public class Ideone {
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!"); }
}
cHVibGljIGNsYXNzIElkZW9uZSB7CgogICAgCiAgICAgICAgcHVibGljIHN0YXRpYyBmaW5hbCBpbnQgRFhbXSA9IHsxLDAsLTEsMH07CiAgICAgICAgcHVibGljIHN0YXRpYyBmaW5hbCBpbnQgRFlbXSA9IHswLDEsMCwgLTF9OwoKCS8vCgkvLyBPem5ha2U6CgkvLwoJLy8gJyMnIHppZAoJLy8gJyAnIGhvZG5pawoJLy8gJ0MnIGNpbGoKCS8vICcuJyBvem5ha2EsIGRhIHNtbyB0cmVudXRubyBsb2thY2lqbyB2a2xqdWNpbGkgdiBwb3QKCS8vCgkKCS8vIFJla3Vyeml2bmEgZnVua2NpamEsIGtpIHBvacWhxI1lIHBvdCBza296aSBsYWJpcmludAoJLy8KCS8vIC0gbGFiaXJpbnQgamUgcG9kYW4geiBkdm9kaW1lbnppb25hbG5pbSBwb2xqZW0gImxhYmlyaW50IgoJLy8gLSAieCIgaW4gInkiIHN0YSB0cmVudXRuaSBrb29yZGluYXRpIHBvdG5pa2EsIGtpIHNlIHByZW1pa2EgcHJvdGkgY2lsanUKCS8vCgoJcHVibGljIHN0YXRpYyBib29sZWFuIG5hamRpUG90KGNoYXJbXVtdIGxhYmlyaW50LCBpbnQgeCwgaW50IHkpIHsKCQkvLyBwcmV2ZXJpIGFsaSBqZSB5LWtvb3JkaW5hdGEgdmVsamF2bmEKICAgICAgICAgICAgICAgIGlmKHkgPCAwIHx8IHkgPiBsYWJpcmludC5sZW5ndGgpCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwkJCgkJCgkJLy8gcHJldmVyaSBhbGkgamUgeC1rb29yZGluYXRhIHZlbGphdm5hCiAgICAgICAgICAgICAgICBpZih4IDwgMCB8fCB4ID4gbGFiaXJpbnQubGVuZ3RoKQogICAgICAgICAgICAgICAgICAgIHJldHVybiBmYWxzZTsJCQkJCgkJCQkKCQkvLyBwcmV2ZXJpIGFsaSBzbW8gcHJpc3BlbGkgZG8gY2lsamE/CiAgICAgICAgICAgICAgICBpZihsYWJpcmludFt4XVt5XSA9PSAnQycpCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7CQkJCQoJCQkJCgkJLy8gYWxpIGplIG5hIHRyZW51dG5pIGxva2FjaWppIHppZD8KCQlpZihsYWJpcmludFt4XVt5XSA9PSAnIycpCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwoJCQkJCgkJLy8gYWxpIHNtbyB2IHRlaiB0b2NraSDFvmUgYmlsaT8KCQlpZihsYWJpcmludFt4XVt5XSA9PSAnLicpCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwoJCQkJCgkJLy8gxI1lIHNtbyBwcmlzcGVsaSBkbyBzZW0sIHBvbWVuaSwgZGEgc21vIGl6dmVkbGkgdmVsamF2bmkgcHJlbWlrCgkJY2hhciB0ZW1wID0gbGFiaXJpbnRbeF1beV07CiAgICAgICAgICAgICAgICBsYWJpcmludFt4XVt5XSA9ICcuJzsKCQkJCQkJCgkJZm9yKGludCBpID0gMDsgaSA8IDQ7IGkrKyl7CiAgICAgICAgICAgICAgICAgICAgaWYobmFqZGlQb3QobGFiaXJpbnQsIHggKyBEWFtpXSwgeSArIERZW2ldKSkKICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgICAgICAgICB9CgkJCQkKCQkvLyDEjWUgc21vIHByacWhbGkgZG8gc2VtLCBwb21lbmksIGRhIHRhIHBvbG/FvmFqIG5pIG5hIHBvdGkgZG8gY2lsamEKCQlsYWJpcmludFt4XVt5XSA9IHRlbXA7CgoJCXJldHVybiBmYWxzZTsKCX0KCQoJcHVibGljIHN0YXRpYyB2b2lkIGl6cGlzKGNoYXJbXVtdIGxhYmlyaW50KQoJewoJCWZvciAoaW50IGkgPSAwOyBpIDwgbGFiaXJpbnQubGVuZ3RoOyBpKyspCgkJewoJCQlmb3IgKGludCBqID0gMDsgIGogPCBsYWJpcmludFtpXS5sZW5ndGg7IGorKykKCQkJCVN5c3RlbS5vdXQucHJpbnQobGFiaXJpbnRbaV1bal0pOwoJCQlTeXN0ZW0ub3V0LnByaW50bG4oKTsKCQl9Cgl9CgkKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKCQljaGFyW11bXSBsYWJpcmludCA9IHsKCQkJCXsnIycsJyMnLCcjJywnIycsJyMnLCcjJywnIycsJyMnLCcjJ30sCgkJCQl7JyMnLCcgJywnICcsJyAnLCcgJywnICcsJyMnLCcgJywnIyd9LAoJCQkJeycjJywnICcsJyMnLCcjJywnIycsJyAnLCcjJywnICcsJyMnfSwKCQkJCXsnIycsJyAnLCcjJywnIycsJyMnLCcgJywnIycsJyAnLCcjJ30sCgkJCQl7JyMnLCcgJywnICcsJyAnLCcjJywnIycsJyMnLCcgJywnIyd9LAoJCQkJeycjJywnICcsJyMnLCcgJywnIycsJyAnLCcgJywnICcsJyMnfSwKCQkJCXsnIycsJyAnLCcjJywnICcsJyAnLCcgJywnIycsJyAnLCcjJ30sCgkJCQl7JyMnLCcgJywnIycsJyMnLCcjJywnIycsJyMnLCcgJywnIyd9LAoJCQkJeycjJywnICcsJyAnLCcgJywnIycsJyAnLCcgJywnQycsJyMnfSwKCQkJCXsnIycsJyMnLCcjJywnIycsJyMnLCcjJywnIycsJyMnLCcjJ319OwoKCQlTeXN0ZW0ub3V0LnByaW50bG4oIkl6Z2xlZCBsYWJpcmludGE6Iik7CgkJaXpwaXMobGFiaXJpbnQpOwoKCQlTeXN0ZW0ub3V0LnByaW50bG4oIlxuTmFqZGVuYSBwb3Qgc2tvemkgbGFiaXJpbnQ6Iik7CgkJLy8gcG9pxaHEjWltbyBpemhvZCBpeiBsYWJpcmludGEgLSBpemhvZGnFocSNbmkgcG9sb8W+YWogamUgbmEga29vcmRpbmF0aSAoeD01LHk9MykKCQlpZiAobmFqZGlQb3QobGFiaXJpbnQsIDUsIDMpKQoJCQlpenBpcyhsYWJpcmludCk7CgkJZWxzZQoJCQlTeXN0ZW0ub3V0LnByaW50bG4oIk5lIG5hamRlbSBwb3RpIHNrb3ppIGxhYmlyaW50ISIpOwoJfQp9