public class Labirint {
public static final int DX[] = {1,0,-1,0};
public static final int DY[] = {0,1,0, -1};
//
// Oznake:
//
// '#' zid
// ' ' hodnik
// 'C' cilj
// '.' oznaka, da smo trenutno lokacijo vkljucili v pot
//
// Rekurzivna funkcija, ki poišče pot skozi labirint
//
// - labirint je podan z dvodimenzionalnim poljem "labirint"
// - "x" in "y" sta trenutni koordinati potnika, ki se premika proti cilju
//
public static boolean najdiPot(char[][] labirint, int x, int y) {
// preveri ali je y-koordinata veljavna
if(y < 0 || y > labirint.length)
return false;
// preveri ali je x-koordinata veljavna
if(x < 0 || x > labirint.length)
return false;
// preveri ali smo prispeli do cilja?
if(labirint[x][y] == 'C')
return true;
// ali je na trenutni lokaciji zid?
if(labirint[x][y] == '#')
return false;
// ali smo v tej tocki že bili?
if(labirint[x][y] == '.')
return false;
// če smo prispeli do sem, pomeni, da smo izvedli veljavni premik
char temp = labirint[x][y];
labirint[x][y] = '.';
for(int i = 0; i < 4; i++){
if(najdiPot(labirint, x + DX[i], y + DY[i]))
return true;
}
// če smo prišli do sem, pomeni, da ta položaj ni na poti do cilja
labirint[x][y] = temp;
return false;
}
public static void izpis(char[][] labirint)
{
for (int i = 0; i < labirint.length; i++)
{
for (int j = 0; j < labirint[i].length; j++)
System.
out.
print(labirint
[i
][j
]); }
}
public static void main
(String[] args
) { char[][] labirint = {
{'#','#','#','#','#','#','#','#','#'},
{'#',' ',' ',' ',' ',' ','#',' ','#'},
{'#',' ','#','#','#',' ','#',' ','#'},
{'#',' ','#','#','#',' ','#',' ','#'},
{'#',' ',' ',' ','#','#','#',' ','#'},
{'#',' ','#',' ','#',' ',' ',' ','#'},
{'#',' ','#',' ',' ',' ','#',' ','#'},
{'#',' ','#','#','#','#','#',' ','#'},
{'#',' ',' ',' ','#',' ',' ','C','#'},
{'#','#','#','#','#','#','#','#','#'}};
System.
out.
println("Izgled labirinta:"); izpis(labirint);
System.
out.
println("\nNajdena pot skozi labirint:"); // poiščimo izhod iz labirinta - izhodiščni položaj je na koordinati (x=5,y=3)
if (najdiPot(labirint, 5, 3))
izpis(labirint);
else
System.
out.
println("Ne najdem poti skozi labirint!"); }
}
cHVibGljIGNsYXNzIExhYmlyaW50IHsKCiAgICAKICAgICAgICBwdWJsaWMgc3RhdGljIGZpbmFsIGludCBEWFtdID0gezEsMCwtMSwwfTsKICAgICAgICBwdWJsaWMgc3RhdGljIGZpbmFsIGludCBEWVtdID0gezAsMSwwLCAtMX07CgoJLy8KCS8vIE96bmFrZToKCS8vCgkvLyAnIycgemlkCgkvLyAnICcgaG9kbmlrCgkvLyAnQycgY2lsagoJLy8gJy4nIG96bmFrYSwgZGEgc21vIHRyZW51dG5vIGxva2FjaWpvIHZrbGp1Y2lsaSB2IHBvdAoJLy8KCQoJLy8gUmVrdXJ6aXZuYSBmdW5rY2lqYSwga2kgcG9pxaHEjWUgcG90IHNrb3ppIGxhYmlyaW50CgkvLwoJLy8gLSBsYWJpcmludCBqZSBwb2RhbiB6IGR2b2RpbWVuemlvbmFsbmltIHBvbGplbSAibGFiaXJpbnQiCgkvLyAtICJ4IiBpbiAieSIgc3RhIHRyZW51dG5pIGtvb3JkaW5hdGkgcG90bmlrYSwga2kgc2UgcHJlbWlrYSBwcm90aSBjaWxqdQoJLy8KCglwdWJsaWMgc3RhdGljIGJvb2xlYW4gbmFqZGlQb3QoY2hhcltdW10gbGFiaXJpbnQsIGludCB4LCBpbnQgeSkgewoJCS8vIHByZXZlcmkgYWxpIGplIHkta29vcmRpbmF0YSB2ZWxqYXZuYQogICAgICAgICAgICAgICAgaWYoeSA8IDAgfHwgeSA+IGxhYmlyaW50Lmxlbmd0aCkKICAgICAgICAgICAgICAgICAgICByZXR1cm4gZmFsc2U7CQkKCQkKCQkvLyBwcmV2ZXJpIGFsaSBqZSB4LWtvb3JkaW5hdGEgdmVsamF2bmEKICAgICAgICAgICAgICAgIGlmKHggPCAwIHx8IHggPiBsYWJpcmludC5sZW5ndGgpCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwkJCQkKCQkJCQoJCS8vIHByZXZlcmkgYWxpIHNtbyBwcmlzcGVsaSBkbyBjaWxqYT8KICAgICAgICAgICAgICAgIGlmKGxhYmlyaW50W3hdW3ldID09ICdDJykKICAgICAgICAgICAgICAgICAgICByZXR1cm4gdHJ1ZTsJCQkJCgkJCQkKCQkvLyBhbGkgamUgbmEgdHJlbnV0bmkgbG9rYWNpamkgemlkPwoJCWlmKGxhYmlyaW50W3hdW3ldID09ICcjJykKICAgICAgICAgICAgICAgICAgICByZXR1cm4gZmFsc2U7CgkJCQkKCQkvLyBhbGkgc21vIHYgdGVqIHRvY2tpIMW+ZSBiaWxpPwoJCWlmKGxhYmlyaW50W3hdW3ldID09ICcuJykKICAgICAgICAgICAgICAgICAgICByZXR1cm4gZmFsc2U7CgkJCQkKCQkvLyDEjWUgc21vIHByaXNwZWxpIGRvIHNlbSwgcG9tZW5pLCBkYSBzbW8gaXp2ZWRsaSB2ZWxqYXZuaSBwcmVtaWsKCQljaGFyIHRlbXAgPSBsYWJpcmludFt4XVt5XTsKICAgICAgICAgICAgICAgIGxhYmlyaW50W3hdW3ldID0gJy4nOwoJCQkJCQkKCQlmb3IoaW50IGkgPSAwOyBpIDwgNDsgaSsrKXsKICAgICAgICAgICAgICAgICAgICBpZihuYWpkaVBvdChsYWJpcmludCwgeCArIERYW2ldLCB5ICsgRFlbaV0pKQogICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICAgICAgICAgIH0KCQkJCQoJCS8vIMSNZSBzbW8gcHJpxaFsaSBkbyBzZW0sIHBvbWVuaSwgZGEgdGEgcG9sb8W+YWogbmkgbmEgcG90aSBkbyBjaWxqYQoJCWxhYmlyaW50W3hdW3ldID0gdGVtcDsKCgkJcmV0dXJuIGZhbHNlOwoJfQoJCglwdWJsaWMgc3RhdGljIHZvaWQgaXpwaXMoY2hhcltdW10gbGFiaXJpbnQpCgl7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBsYWJpcmludC5sZW5ndGg7IGkrKykKCQl7CgkJCWZvciAoaW50IGogPSAwOyAgaiA8IGxhYmlyaW50W2ldLmxlbmd0aDsgaisrKQoJCQkJU3lzdGVtLm91dC5wcmludChsYWJpcmludFtpXVtqXSk7CgkJCVN5c3RlbS5vdXQucHJpbnRsbigpOwoJCX0KCX0KCQoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewoJCWNoYXJbXVtdIGxhYmlyaW50ID0gewoJCQkJeycjJywnIycsJyMnLCcjJywnIycsJyMnLCcjJywnIycsJyMnfSwKCQkJCXsnIycsJyAnLCcgJywnICcsJyAnLCcgJywnIycsJyAnLCcjJ30sCgkJCQl7JyMnLCcgJywnIycsJyMnLCcjJywnICcsJyMnLCcgJywnIyd9LAoJCQkJeycjJywnICcsJyMnLCcjJywnIycsJyAnLCcjJywnICcsJyMnfSwKCQkJCXsnIycsJyAnLCcgJywnICcsJyMnLCcjJywnIycsJyAnLCcjJ30sCgkJCQl7JyMnLCcgJywnIycsJyAnLCcjJywnICcsJyAnLCcgJywnIyd9LAoJCQkJeycjJywnICcsJyMnLCcgJywnICcsJyAnLCcjJywnICcsJyMnfSwKCQkJCXsnIycsJyAnLCcjJywnIycsJyMnLCcjJywnIycsJyAnLCcjJ30sCgkJCQl7JyMnLCcgJywnICcsJyAnLCcjJywnICcsJyAnLCdDJywnIyd9LAoJCQkJeycjJywnIycsJyMnLCcjJywnIycsJyMnLCcjJywnIycsJyMnfX07CgoJCVN5c3RlbS5vdXQucHJpbnRsbigiSXpnbGVkIGxhYmlyaW50YToiKTsKCQlpenBpcyhsYWJpcmludCk7CgoJCVN5c3RlbS5vdXQucHJpbnRsbigiXG5OYWpkZW5hIHBvdCBza296aSBsYWJpcmludDoiKTsKCQkvLyBwb2nFocSNaW1vIGl6aG9kIGl6IGxhYmlyaW50YSAtIGl6aG9kacWhxI1uaSBwb2xvxb5haiBqZSBuYSBrb29yZGluYXRpICh4PTUseT0zKQoJCWlmIChuYWpkaVBvdChsYWJpcmludCwgNSwgMykpCgkJCWl6cGlzKGxhYmlyaW50KTsKCQllbHNlCgkJCVN5c3RlbS5vdXQucHJpbnRsbigiTmUgbmFqZGVtIHBvdGkgc2tvemkgbGFiaXJpbnQhIik7Cgl9Cn0=