บทความนี้แบ่งปันอัลกอริทึมเขาวงกตเวอร์ชัน Java โดยใช้สแต็กซึ่งส่วนใหญ่จะตรวจสอบการใช้สแต็กสำหรับการอ้างอิงของคุณ เนื้อหาเฉพาะมีดังนี้
แนวคิดหลักมีดังนี้:
ทำ {ถ้า (ตำแหน่งปัจจุบันสามารถส่งผ่าน) {ทำเครื่องหมายตำแหน่งนี้ที่ผ่านไปแล้ว บันทึกตำแหน่งปัจจุบันและรวมเข้ากับสแต็ก ถ้า (ตำแหน่งปัจจุบันคือจุดสิ้นสุด) {โปรแกรมสิ้นสุด; } รับตำแหน่งถัดไป; } else {ถ้า (สแต็กไม่ว่าง) {ออกจากสแต็ก; ในขณะที่ (ทิศทางตำแหน่งปัจจุบันคือ 4 และสแต็กไม่ว่างเปล่า) {ทำเครื่องหมายตำแหน่งปัจจุบันที่ไม่สามารถเคลื่อนย้ายได้ ออกจากสแต็ค; } ถ้า (ทิศทางของตำแหน่งปัจจุบันน้อยกว่า 4) {ทิศทาง +1; เข้าสู่สแต็กอีกครั้ง รับตำแหน่งต่อไป }}}} ในขณะที่ (สแต็กไม่ว่างเปล่า);รหัส Java มีดังนี้:
นำเข้า java.util.stack; เขาวงกตระดับสาธารณะ {// สแต็คสแต็คส่วนตัว <Mazenode> stack = สแต็คใหม่ <maze.mazenode> (); // เขาวงกตส่วนตัว int [] [] เขาวงกต = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, {1,0,1,1,0,0,0,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1,1s 1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1s 1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1s0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1s 0,0,1,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1s1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1s 1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1s ,, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1s ,, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1s ,, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1s {1,0,0,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0s0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0s {1,1,0,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1s ,, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1s 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1s ,, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1,1s1,1,1,1,1,1,1,1,1,1,1,1,1s ส่วนตัวคงที่ int maze maze_size_x = 14; ส่วนตัวคงที่ int maze_size_y = 17; INT int สุดท้ายคงที่ส่วนตัว end_x = 12; INT Int สุดท้ายคงที่ส่วนตัว end_y = 15; โมฆะส่วนตัวเริ่มต้น () {สำหรับ (int i = 0; i <maze_size_x; i ++) {สำหรับ (int j = 0; j <maze_size_y; j ++) {mark [i] [j] = 0; }}} กระบวนการโมฆะสาธารณะ () {initmark (); ตำแหน่ง curpos = ตำแหน่งใหม่ (1, 1); ทำ {// เส้นทางนี้สามารถใช้ถ้า (เขาวงกต [curpos.x] [curpos.y] == 0 && mark [curpos.x] [curpos.y] == 0) {mark [curpos.x] [curpos.y] = 1; stack.push (mazenode ใหม่ (curpos, 1)); // จุดสิ้นสุดถ้า (curpos.x == end_x && curpos.y == end_y) {return; } curpos = nextpos (curpos, stack.peek (). ทิศทาง); } // ไม่สามารถไปอื่น {ถ้า (! stack.isempty ()) {mazenode curnode = stack.pop (); ในขณะที่ (curnode.direction == 4 &&! stack.isempty ()) {// ถ้ามีการทดลองทั้ง 4 ทิศทางของตำแหน่งปัจจุบันแล้วทำเครื่องหมายตำแหน่งที่ไม่สามารถเคลื่อนย้ายและทำเครื่องหมาย [curnode.position.x] [curnode.position.y] = 1; curnode = stack.pop (); } if (curnode.direction <4) {curnode.direction ++; // direction +1 stack.push (curnode); // re-enter curpos = nextpos (curnode.position, curnode.direction); // รับตำแหน่งถัดไป}}} } โมฆะสาธารณะ drawmaze () {สำหรับ (int i = 0; i <maze.length; i ++) {สำหรับ (int j = 0; j <เขาวงกต [0] .length; j ++) {system.out.print (เขาวงกต [i] [j]); } system.out.print ("/n"); } system.out.print ("/n"); } โมฆะสาธารณะ drawresult () {initmark (); โหนด Mazenode; ในขณะที่ (! stack.isempty ()) {node = stack.pop (); mark [node.position.x] [node.position.y] = 1; } สำหรับ (int i = 0; i <mark.length; i ++) {สำหรับ (int j = 0; j <mark [0] .length; j ++) {system.out.print (mark [i] [j]); } system.out.print ("/n"); } system.out.print ("/n"); } // บันทึกตำแหน่งของคะแนนในตำแหน่งคลาสเขาวงกต {int x; int y; ตำแหน่งสาธารณะ (int x, int y) {this.x = x; this.y = y; }} // โหนดในคลาสสแต็ก mazenode {ตำแหน่งตำแหน่ง; ทิศทาง int; mazenode สาธารณะ (ตำแหน่ง pos) {this.position = pos; } mazenode สาธารณะ (ตำแหน่ง pos, int dir) {this.position = pos; this.direction = dir; }} // ตำแหน่งถัดไปเริ่มต้นจากทางขวาตำแหน่งสาธารณะตามเข็มนาฬิกา NextPos (ตำแหน่งตำแหน่ง, ทิศทาง int) {ตำแหน่ง newPosition = ตำแหน่งใหม่ (position.x, position.y); สวิตช์ (ทิศทาง) {กรณีที่ 1: newposition.y += 1; หยุดพัก; กรณีที่ 2: newposition.x += 1; หยุดพัก; กรณีที่ 3: newposition.y -= 1; หยุดพัก; กรณีที่ 4: newposition.x -= 1; หยุดพัก; ค่าเริ่มต้น: break; } ส่งคืนตำแหน่งใหม่; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {เขาวงกตเขาวงกต = ใหม่เขาวงกต (); Maze.drawmaze (); Maze.process (); Maze.drawresult (); -ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น