Miten tämän pystyy tekemään kätevämmin?
import java.util.Random;
public class Sokkelo_etsin {
public static void main(String[] args){
//Tämä etsii sokkelosta ulospääsyä.
//0 tarkoittaa reittiä, missä hahmo voi liikkua.
//Hahmo voi liikkua alas ja oikealle.
//Jos hahmo menee väärään suuntaan, tehdään peruutus.
Random sattuma = new Random();
int sokkelo[][] = {{0,1,1,1,1,1,1},{0,0,0,0,0,0,0},{0,1,1,1,1,1,1},{0,0,0,1,1,1,1},{1,1,0,0,0,0,1},{1,1,0,1,1,1,1},{1,1,1,1,1,1,1}};
//Hahmon koordinaatit
int kohtaY = 0;
int kohtaX = 0;
int suunta = 0;
//Tallennetaan, mutkat jos joudutaan peruuttamaan.
int mutkaY[] = new int[7];
int mutkaX[] = new int[7];
int indeksi = 0;
boolean peruutus = false;
//Näytetään sokkelo.
System.out.println(" 1 2 3 4 5 6 7");
System.out.println("________________");
for (int y = 0; y < 7; y++){
System.out.print((y+1) + ":");
for (int x = 0; x < 7; x++){
System.out.print(sokkelo[y][x] + " ");
}
System.out.println("");
}
System.out.println("Kohta Y:" + (kohtaY+1));
System.out.println("Kohta X: " + (kohtaX+1));
//Etsitään reitti.
//Katsotaan ensin alas ja sitten oikealle, muuten tehdään peruutus.
while (kohtaY < 6 && kohtaX < 6){
if (sokkelo[kohtaY+1][kohtaX] == 0 && sokkelo[kohtaY][kohtaX+1] == 0 && peruutus == false){
//Tallennetaan mahdollista peruutusta varten.
mutkaY[indeksi] = kohtaY;
mutkaX[indeksi] = kohtaX;
indeksi++;
}
if (sokkelo[kohtaY+1][kohtaX] == 0 || (sokkelo[kohtaY][kohtaX+1] == 0 && peruutus == true)){
if (sokkelo[kohtaY][kohtaX+1] == 0 && peruutus == true){
kohtaX++;
suunta = 2;
}
else {
kohtaY++;
suunta = 1;
}
peruutus = false;
}
else if (sokkelo[kohtaY][kohtaX+1] == 0 || (sokkelo[kohtaY+1][kohtaX] == 0 && peruutus == true)){
if (sokkelo[kohtaY+1][kohtaX] == 0 && peruutus == true){
kohtaY++;
suunta = 1;
}
else {
kohtaX++;
suunta = 2;
}
peruutus = false;
}
else {
if (indeksi > 0){
indeksi--;
}
peruutus = true;
}
if (peruutus == true){
//Suoritetaan peruutus
while (kohtaY > mutkaY[indeksi]){
kohtaY--;
}
while (kohtaX > mutkaX[indeksi]){
kohtaX--;
}
}
System.out.println("Kohta Y:" + (kohtaY+1));
System.out.println("Kohta X: " + (kohtaX+1));
}
}
}pystyt toteuttamaan tuon kätevämmin rekursiivisesti.
Mutta mitä järkeä ohjelmasi tulostuksessa on? Tulostuksesta ei saa selvää, löytyikö reittiä ulos, vaan se tulostaa jokaisen kohdan taulukosta, missä on 0. Kaiken lisäksi se tulostaa useamman kerran saman kohdan.
Tässä oma rekursiivinen toteutukseni javascriptillä, voit ajaa sen vaikka osoitteessa playcode.io.
const sokkelo = [
[0, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 1, 1, 1, 1],
[1, 1, 0, 0, 0, 0, 1],
[1, 1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1]
]
let ratkaisut = []
const etsiPolutRekursiivisesti = (polku) => {
const nykyinenPiste = polku[polku.length - 1]
if(nykyinenPiste.includes(6)) ratkaisut.push(polku)
else {
const [y, x] = nykyinenPiste
if(sokkelo[y + 1][x] === 0) {
etsiPolutRekursiivisesti(polku.concat([
[y + 1, x]
]))
}
if(sokkelo[y][x + 1] === 0) {
etsiPolutRekursiivisesti(polku.concat([
[y, x + 1]
]))
}
}
}
const tulostaRatkaisut = () => {
if(ratkaisut.length === 0) console.log('Reittiä ei löytynyt')
else {
ratkaisut.forEach((polku, i) => {
let sokkeloKopio = JSON.parse(JSON.stringify(sokkelo))
polku.forEach(([y, x]) => sokkeloKopio[y][x] = 'X')
console.log(`Ratkaisu ${i + 1}:`)
console.table(sokkeloKopio)
})
}
}
console.log('Sokkelo:')
console.table(sokkelo)
etsiPolutRekursiivisesti([[0, 0]])
tulostaRatkaisut()Kätevämmin tekeminen riippuu siitä, mitä kätevyys tarkoittaa. Tässä ongelmassa eräs kätevä ratkaisu on sellainen, josta saadaan tehokkaasti kaikki mahdolliset sokkelon ratkaisut.
Koska liike tapahtuu vain alas ja oikealle, sokkelon umpikujat voi täyttää for-silmukalla takaperin järjestyksessä. Tämän jälkeen mikä tahansa sallittu siirto vie kohti varmaa voittoa.
public class SokkeloKahteenSuuntaan {
public static void tulosta(int sokkelo[][]) {
for (int i = 0; i < sokkelo.length; ++i) {
for (int j = 0; j < sokkelo[i].length; ++j) {
System.out.print(sokkelo[i][j] == 0 ? "." : "#");
}
System.out.println();
}
}
public static void täytäUmpikujat(int sokkelo[][]) {
for (int i = sokkelo.length - 2; i >= 0; --i) {
for (int j = sokkelo[i].length - 2; j >= 0; --j) {
if (sokkelo[i + 1][j] == 1 && sokkelo[i][j + 1] == 1) {
// Jos ruudusta ei pääse alas eikä oikealle, se on umpikuja.
sokkelo[i][j] = 1;
}
}
}
}
static java.util.Random sattuma = new java.util.Random();
public static void tulostaSatunnainenReitti(int sokkelo[][]) {
int x = 0, y = 0, h = sokkelo.length, w = sokkelo[0].length;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
System.out.print(y == i && x == j ? "o" : sokkelo[i][j] == 0 ? "." : "#");
if (y == i && x == j && y + 1 < h && x + 1 < w) {
boolean a = y + 1 < h && sokkelo[y + 1][x] == 0;
boolean o = x + 1 < w && sokkelo[y][x + 1] == 0;
if (a && (!o || sattuma.nextBoolean())) {
y += 1;
} else if (o) {
x += 1;
}
}
}
System.out.println();
}
}
public static void main(String[] args) {
int sokkelo[][] = {
{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
{0,1,0,1,0,0,1,1,1,0,1,0,0,0,0,1,0,1,0},
{0,1,0,0,0,1,0,1,1,0,1,1,1,1,1,1,0,1,0},
{0,1,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
{0,1,0,0,1,0,1,0,1,1,1,1,0,0,1,1,1,0,0},
{0,1,1,1,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,0,1},
{0,0,1,1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1}
};
tulosta(sokkelo);
täytäUmpikujat(sokkelo);
System.out.println("========================================");
tulostaSatunnainenReitti(sokkelo);
}
}Aihe on jo aika vanha, joten et voi enää vastata siihen.