อาร์เรย์สี่เหลี่ยม M × N แสดงถึงเขาวงกตและ 0 และ 1 เป็นตัวแทนของเส้นทางและอุปสรรคในเขาวงกตตามลำดับ ออกแบบโปรแกรมเพื่อค้นหาเส้นทางจากทางเข้าสู่ทางออกสำหรับเขาวงกตการตั้งค่าใด ๆ หรือสรุปว่าไม่มีเส้นทาง
(1) เอาต์พุตกราฟของเขาวงกตตามอาร์เรย์สองมิติ
(2) สำรวจสี่ทิศทางของเขาวงกต: ขวาคือทางด้านขวาลงไปทางด้านซ้ายคือทางซ้ายและขึ้นไปทางบนและส่งออกเส้นทางเดินจากทางเข้าสู่ทางออก
ตัวอย่าง:
มุมซ้ายบน (1, 1) เป็นทางเข้าและมุมล่างขวา (8, 9) คือทางออก
คุณสามารถใช้วิธีการย้อนรอยนั่นคือเริ่มต้นจากทางเข้าและสำรวจในทิศทางที่แน่นอน หากสามารถทำได้ให้ก้าวไปข้างหน้าต่อไป มิฉะนั้นให้ล่าถอยไปตามเส้นทางดั้งเดิมให้สำรวจไปในทิศทางอื่นจนกว่าจะถึงตำแหน่งทางออกและค้นหาเส้นทาง หากมีการสำรวจเส้นทางที่เป็นไปได้ทั้งหมดและยังไม่ถึงทางออกชุดเขาวงกตจะไม่มีเส้นทาง
นำเข้า java.util.*; ตำแหน่งคลาส {ตำแหน่งสาธารณะ () {} ตำแหน่งสาธารณะ (แถว int, int col) {this.col = col; this.row = row; } public String toString () {return "(" + row + "," + col + ")"; } Int Row; int col;} คลาสเขาวงกต {เขาวงกตสาธารณะ () {เขาวงกต = ใหม่ int [15] [15]; stack = ใหม่สแต็ก <Socount> (); p = บูลีนใหม่ [15] [15]; } /** การสร้างเขาวงกต* / โมฆะสาธารณะ init () {สแกนเนอร์สแกนเนอร์ = สแกนเนอร์ใหม่ (System.in); System.out.println ("โปรดป้อนจำนวนแถวของเขาวงกต"); row = scanner.nextint (); System.out.println ("โปรดป้อนจำนวนคอลัมน์ของเขาวงกต"); col = scanner.nextint (); System.out.println ("โปรดป้อน" + แถว + "แถว" + col + "คอลัมน์เขาวงกต"); int temp = 0; สำหรับ (int i = 0; i <row; ++ i) {สำหรับ (int j = 0; j <col; ++ j) {temp = scanner.nextint (); เขาวงกต [i] [j] = อุณหภูมิ; p [i] [j] = false; }}} /** กลับไปที่เขาวงกตเพื่อดูว่ามีทางออก* / โมฆะสาธารณะ findpath () {// ให้วงกลมของผนังรอบบ้านของอุณหภูมิของเขาวงกต สำหรับ (int i = 0; i <row +2; ++ i) {สำหรับ (int j = 0; j <col +2; ++ j) {temp [0] [j] = 1; อุณหภูมิ [แถว + 1] [j] = 1; temp [i] [0] = temp [i] [col + 1] = 1; }} // คัดลอกเขาวงกตดั้งเดิมไปยังเขาวงกตใหม่สำหรับ (int i = 0; i <row; ++ i) {สำหรับ (int j = 0; j <col; ++ j) {temp [i +1] [j +1] = เขาวงกต [i] [j]; }} // เริ่มสอบถามตามเข็มนาฬิกาจากมุมซ้ายบน int i = 1; int j = 1; p [i] [j] = true; stack.push (ตำแหน่งใหม่ (i, j)); ในขณะที่ (! stack.empty () && (! (i == (แถว) && (j == col))))) {if ((temp [i] [j + 1] == 0) && (p [i] [j + 1] == เท็จ)) {p [i] [j + 1] = true; stack.push (ตำแหน่งใหม่ (i, j + 1)); J ++; } อื่นถ้า ((temp [i + 1] [j] == 0) && (p [i + 1] [j] == false)) {p [i + 1] [j] = true; stack.push (ตำแหน่งใหม่ (i + 1, j)); i ++; } อื่นถ้า ((temp [i] [j - 1] == 0) && (p [i] [j - 1] == เท็จ)) {p [i] [j - 1] = true; stack.push (ตำแหน่งใหม่ (i, j - 1)); J--; } อื่นถ้า ((temp [i - 1] [j] == 0) && (p [i - 1] [j] == false)) {p [i - 1] [j] = true; stack.push (ตำแหน่งใหม่ (i - 1, j)); ฉัน--; } else {stack.pop (); if (stack.empty ()) {break; } i = stack.peek (). แถว; j = stack.peek (). col; }} สแต็ก <Socount> newPOS = ใหม่สแต็ก <SOACHTURE> (); if (stack.empty ()) {break; } i = stack.peek (). แถว; j = stack.peek (). col; }} สแต็ก <Socount> newPOS = ใหม่สแต็ก <SOACHTURE> (); if (stack.empty ()) {system.out.println ("ไม่มีเส้นทาง"); } else {system.out.println ("มีเส้นทาง"); System.out.println ("เส้นทางมีดังนี้:"); ในขณะที่ (! stack.empty ()) {position pos = ตำแหน่งใหม่ (); pos = stack.pop (); newpos.push (POS); }} / * * เส้นทางเอาต์พุตกราฟิก * * / สตริงผลลัพธ์ [] [] = สตริงใหม่ [แถว+1] [col+1]; สำหรับ (int k = 0; k <row; ++ k) {สำหรับ (int t = 0; t <col; ++ t) {ผลลัพธ์ [k] [t] = (เขาวงกต [k] [t])+""; }} ในขณะที่ (! newpos.empty ()) {ตำแหน่ง p1 = newpos.pop (); ผลลัพธ์ [P1.Row-1] [P1.COL-1] = "#"; } สำหรับ (int k = 0; k <row; ++ k) {สำหรับ (int t = 0; t <col; ++ t) {system.out.print (resault [k] [t]+"/t"); } system.out.println (); }} int maze [] []; INT แถวส่วนตัว = 9; ส่วนตัว int col = 8; สแต็ค <Soction> สแต็ค; บูลีน p [] [] = null;} คลาสสวัสดี {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {เขาวงกตตัวอย่าง = new Maze (); demo.init (); demo.findpath (); - ตัวอย่างการรัน:
โปรดป้อนจำนวนแถวของเขาวงกต
3
โปรดป้อนจำนวนคอลัมน์ในเขาวงกต
3
โปรดป้อนเขาวงกต 3 แถวและ 3 คอลัมน์
0 1 1
0 0 1
1 0 0
เส้นทางมีดังนี้:
โปรดป้อนจำนวนแถวของเขาวงกต
9
โปรดป้อนจำนวนคอลัมน์ในเขาวงกต
8
โปรดป้อนเขาวงกต 9 แถวและ 8 คอลัมน์
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 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
เส้นทางมีดังนี้:
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น