本文目錄一覽：
求Java關於迷宮的算法（用棧實現）
package com.Albert.LabyringhStack;
public class Point {
int x;
int y;
int direction; //direction指向此點附近的一個點 應該有四個 編號為1 2 3 4
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getDirection() {
return direction;
}
public void setDirection(int direction) {
this.direction = direction;
}
public void addDirection(){
this.direction++;
}
public Point() {
}
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
this.direction = 1;
}
public Point(int x, int y, int direction) {
super();
this.x = x;
this.y = y;
this.direction = direction;
}
}
package com.Albert.LabyringhStack;
import java.util.*;
public class LabyringhStack {
public Point S;
public Point F;
char[][] mazemap;
StackPoint path;
public LabyringhStack() {
}
public LabyringhStack(char[][] ma) { //初始化 存入數組
this.mazemap = new char[ma.length][ma[0].length];
for(int i=0;ima.length;i++){
for(int j=0;jma[0].length;j++){ //mazemap[0]必須有元素 不可為空
this.mazemap[i][j] = ma[i][j];
}
}
S = returnPlace(‘S’);
F = returnPlace(‘F’);
}
public Point returnPlace(char s){ //返回數組中字符的位置
Point point = new Point();
for(int i=0;ithis.mazemap.length;i++){
for(int j=0;jthis.mazemap[0].length;j++){ //mazemap[0]必須有元素 不可為空
if(this.mazemap[i][j]==s)
{ point.setX(i);
point.setY(j);
point.setDirection(1);
}
}
}
return point;
}
public char returnChar(Point point){
if(point.getX()=0point.getY()=0)
return this.mazemap[point.getX()][point.getY()];
else
return ‘#’;
}
public void replacePlace(Point point, char s){ //更改特定位置處的字符
mazemap[point.getX()][point.getY()] = s;
}
public void printPath(){
StackPoint tempPath = new StackPoint();
while(!path.empty()){ //對棧進行反序
tempPath.push(path.pop());
}
while(!tempPath.empty()){
System.out.print(“(“+tempPath.peek().getX()+”,”+tempPath.pop().getY()+”)”);
}
}
public boolean getPath(){ //取得路徑的算法 如果有路徑就返回真
path = new StackPoint();
S.setDirection(1);
path.push(S);
replacePlace(S, ‘X’);
while(!path.empty()){
Point nowPoint = path.peek(); //取得當前位置
if(nowPoint.getX()==F.getX()nowPoint.getY()==F.getY()){
//printPath();
return true;
}
Point temp = new Point(); //存放下一個可走的位置
int find = 0; //標誌 是否可向下走
while(nowPoint.getDirection()5find==0){
switch(nowPoint.getDirection()){
case 1:temp = new Point(nowPoint.getX(),nowPoint.getY()-1,1); break; //取得當前位置左邊的位置
case 2:temp = new Point(nowPoint.getX()+1,nowPoint.getY(),1); break;//取得當前位置下邊的位置
case 3:temp = new Point(nowPoint.getX(),nowPoint.getY()+1,1); break;//取得當前位置右邊的位置
case 4:temp = new Point(nowPoint.getX()-1,nowPoint.getY(),1); break;//取得當前位置上邊的位置
}
nowPoint.addDirection(); //指向下一個需要驗證的點
if(returnChar(temp)==’O’||returnChar(temp)==’F’) find = 1; //如果能向下走則置為1
}
if(find==1){ //如果可走就進棧
replacePlace(temp, ‘X’); //設置成X 防止回走
// printArr();
path.push(temp);
}else{ //如果不可走就退棧
replacePlace(nowPoint, ‘O’);
path.pop();
}
}
return false;
}
public void printArr(){
for(int i=0;imazemap.length;i++){
for(int j=0;jmazemap[0].length;j++){ //mazemap[0]必須有元素 不可為空
System.out.print(mazemap[i][j]);
}
System.out.println();
}
System.out.println();
}
}
package com.Albert.LabyringhStack;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] mazemap = {
{‘M’,’M’,’M’,’M’,’M’,’M’,’M’,’M’},
{‘M’,’S’,’O’,’O’,’M’,’M’,’M’,’M’},
{‘M’,’M’,’M’,’O’,’M’,’M’,’M’,’M’},
{‘M’,’M’,’O’,’O’,’O’,’O’,’M’,’M’},
{‘M’,’M’,’M’,’M’,’M’,’F’,’M’,’M’},
{‘M’,’M’,’M’,’M’,’M’,’M’,’M’,’M’},
{‘M’,’M’,’M’,’M’,’M’,’M’,’M’,’M’}
};
LabyringhStack solution = new LabyringhStack(mazemap);
if(solution.getPath()){
System.out.print(“迷宮路徑如下：”);
solution.printPath();
}
else {
System.out.println(“沒有可走的路”);
}
}
}
求走迷宮問題的算法，要求用Java寫的？
public class Maze { private int[][] maze = null;
private int[] xx = { 1, 0, -1, 0 };
private int[] yy = { 0, 1, 0, -1 };
private Queue queue = null; public Maze(int[][] maze) {
this.maze = maze;
queue = new Queue(maze.length * maze.length);
} public void go() {
Point outPt = new Point(maze.length – 1, maze[0].length – 1);
Point curPt = new Point(0, 0);
Node curNode = new Node(curPt, null);
maze[curPt.x][curPt.y] = 2;
queue.entryQ(curNode); while (!queue.isEmpty()) {
curNode = queue.outQ();
for (int i = 0; i xx.length; ++i) {
Point nextPt = new Point();
nextPt.x = (curNode.point).x + xx[i];
nextPt.y = (curNode.point).y + yy[i];
if (check(nextPt)) {
Node nextNode = new Node(nextPt, curNode);
queue.entryQ(nextNode);
maze[nextPt.x][nextPt.y] = 2;
if (nextPt.equals(outPt)) {
java.util.StackNode stack = new java.util.StackNode();
stack.push(nextNode);
while ((curNode = nextNode.previous) != null) {
nextNode = curNode;
stack.push(curNode);
}
System.out.println(“A Path is:”);
while (!stack.isEmpty()) {
curNode = stack.pop();
System.out.println(curNode.point);
}
return;
}
}
}
}
System.out.println(“Non solution!”);
} private boolean check(Point p) {
if (p.x 0 || p.x = maze.length || p.y 0 || p.y = maze[0].length) {
return false;
}
if (maze[p.x][p.y] != 0) {
return false;
}
return true;
} public static void main(String[] args) {
int[][] maze = {
{ 0, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 0, 1, 0, 0 }
};
new Maze(maze).go();
} private class Queue { Node[] array = null;
int size = 0;
int len = 0;
int head = 0;
int tail = 0; public Queue(int n) {
array = new Node[n + 1];
size = n + 1;
} public boolean entryQ(Node node) {
if (isFull()) {
return false;
}
tail = (tail + 1) % size;
array[tail] = node;
len++;
return true;
} public Node outQ() {
if (isEmpty()) {
return null;
}
head = (head + 1) % size;
len–;
return array[head];
} public boolean isEmpty() {
return (len == 0 || head == tail) ? true : false;
} public boolean isFull() {
return ((tail + 1) % size == head) ? true : false;
}
} private class Node { Point point = null;
Node previous = null; public Node() {
this(null,null);
} public Node(Point point, Node node) {
this.point = point;
this.previous = node;
}
} private class Point { int x = 0;
int y = 0; public Point() {
this(0, 0);
} public Point(int x, int y) {
this.x = x;
this.y = y;
} public boolean equals(Point p) {
return (x == p.x) (y == p.y);
} @Override
public String toString() {
return “(” + x + “,” + y + “)”;
}
}
}
java自動走迷宮線程問題
以一個M×N的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。
（1） 根據二維數組，輸出迷宮的圖形。
（2） 探索迷宮的四個方向：RIGHT為向右，DOWN向下，LEFT向左，UP向上，輸出從入口到出口的行走路徑。
java棧實現走迷宮
首先，你要知道走迷宮的思路：就是遇到岔路都往一個方向，比如往右，遇到死路就回頭，回頭遇到岔路繼續往右。
原創文章，作者：WYVM，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/145034.html
微信掃一掃 
支付寶掃一掃 