Array persegi panjang m × n mewakili labirin, dan 0 dan 1 masing -masing mewakili jalur dan hambatan di labirin. Rancang program untuk menemukan jalur dari pintu masuk ke pintu keluar untuk labirin pengaturan apa pun, atau menarik kesimpulan bahwa tidak ada jalan.
(1) Keluaran grafik labirin sesuai dengan array dua dimensi.
(2) Jelajahi empat arah labirin: kanan adalah ke kanan, ke bawah adalah ke bawah, kiri adalah ke kiri, dan ke atas adalah ke atas, dan mengeluarkan jalur berjalan dari pintu masuk ke pintu keluar.
contoh:
Sudut kiri atas (1, 1) adalah pintu masuk, dan sudut kanan bawah (8, 9) adalah pintu keluar.
Anda dapat menggunakan metode backtracking, yaitu mulai dari pintu masuk dan menjelajahi arah tertentu. Jika dapat dilakukan, terus bergerak maju; Jika tidak, retret di sepanjang jalur asli, terus jelajahi ke arah lain sampai posisi keluar, dan temukan jalan. Jika semua jalur yang mungkin dieksplorasi dan pintu keluar tidak tercapai, set labirin tidak memiliki jalur.
impor java.util.*; posisi kelas {posisi publik () {} posisi publik (baris int, int col) {this.col = col; this.row = row; } public string toString () {return "(" + row + "," + col + ")"; } int baris; int col;} class maze {public maze () {maze = new int [15] [15]; stack = new stack <ition> (); p = boolean baru [15] [15]; } /** Membangun labirin* / public void init () {scanner scanner = pemindai baru (system.in); System.out.println ("Harap masukkan jumlah baris labirin"); baris = scanner.nextInt (); System.out.println ("Harap masukkan jumlah kolom labirin"); col = scanner.nextInt (); System.out.println ("Harap masukkan" + baris + "baris" + col + "labirin kolom"); int temp = 0; untuk (int i = 0; i <row; ++ i) {for (int j = 0; j <col; ++ j) {temp = scanner.nextInt (); labirin [i] [j] = temp; p [i] [j] = false; }}} /** Kembali ke labirin untuk melihat apakah ada jalan keluar* / public void findPath () {// Berikan lingkaran dinding di sekitar rumah labirin asli int temp [] [] = int baru [baris + 2] [col + 2]; untuk (int i = 0; i <baris +2; ++ i) {untuk (int j = 0; j <col +2; ++ j) {temp [0] [j] = 1; temp [baris + 1] [j] = 1; temp [i] [0] = temp [i] [col + 1] = 1; }} // Salin labirin asli ke labirin baru untuk (int i = 0; i <row; ++ i) {for (int j = 0; j <col; ++ j) {temp [i +1] [j +1] = labirin [i] [j]; }} // Mulai menanyakan searah jarum jam dari sudut kiri atas int i = 1; int j = 1; p [i] [j] = true; stack.push (posisi baru (i, j)); while (! stack.empty () && (! (i == (baris) && (j == col))))) {if ((Temp [i] [j + 1] == 0) && (p [i] [j + 1] == false)) {p [i] [j + 1] = true; stack.push (posisi baru (i, j + 1)); j ++; } else if ((temp [i + 1] [j] == 0) && (p [i + 1] [j] == false)) {p [i + 1] [j] = true; stack.push (posisi baru (i + 1, j)); i ++; } else if ((temp [i] [j - 1] == 0) && (p [i] [j - 1] == false)) {p [i] [j - 1] = true; stack.push (posisi baru (i, j - 1)); J--; } else if ((temp [i - 1] [j] == 0) && (p [i - 1] [j] == false)) {p [i - 1] [j] = true; stack.push (posisi baru (i - 1, j)); Saya--; } else {stack.pop (); if (stack.empty ()) {break; } i = stack.peek (). baris; j = stack.peek (). col; }} Stack <Position> newPos = new stack <ition> (); if (stack.empty ()) {break; } i = stack.peek (). baris; j = stack.peek (). col; }} Stack <Position> newPos = new stack <ition> (); if (stack.empty ()) {System.out.println ("No Path"); } else {System.out.println ("Ada Path"); System.out.println ("Path adalah sebagai berikut:"); while (! stack.empty ()) {position pos = position baru (); pos = stack.pop (); newpos.push (pos); }} / * * Jalur output grafis * * / hasil string [] [] = string baru [baris+1] [col+1]; untuk (int k = 0; k <row; ++ k) {for (int t = 0; t <col; ++ t) {hasil [k] [t] = (maze [k] [t])+""; }} while (! newpos.empty ()) {position p1 = newpos.pop (); Hasil [p1.row-1] [p1.col-1] = "#"; } untuk (int k = 0; k <row; ++ k) {for (int t = 0; t <col; ++ t) {System.out.print (result [k] [t]+"/t"); } System.out.println (); }} int maze [] []; Private int Row = 9; private int col = 8; Stack <ition> stack; boolean p [] [] = null;} kelas hello {public static void main (string [] args) {maze demo = new maze (); demo.init (); demo.findpath (); }} Contoh Menjalankan:
Harap masukkan jumlah baris labirin
3
Harap masukkan jumlah kolom di labirin
3
Harap masukkan labirin 3 baris dan 3 kolom
0 1 1
0 0 1
1 0 0
Jalannya adalah sebagai berikut:
Harap masukkan jumlah baris labirin
9
Harap masukkan jumlah kolom di labirin
8
Harap masukkan labirin 9 baris dan 8 kolom
0 0 1 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0 0 0
Jalannya adalah sebagai berikut:
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.