Kirjautuminen

Haku

Tehtävät

Kilpailu

Ohjelmoi tekoäly!
Tulokset on julkaistu.
Onnea voittajalle!

Keskustelu: Ohjelmointiongelmat: Java: Sokkelo

Sivu 1 / 1

JRokka [12.01.2020 21:22:52]

Lainaa #

Miten tämän pystyy tekemään kätevämmin?

Koodi

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));


        }
    }
}

AtskaFin [13.01.2020 00:11:11]

Lainaa #

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()

Metabolix [13.01.2020 12:36:51]

Lainaa #

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);
	}
}

Vastaus

Muista lukea kirjoitusohjeet.
Tietoa sivustosta