深度優先的迷宮圖演算法。
N年前的老問題了。
10分不值得做。
Ⅱ JAVA走迷宮問題-怎麼使迷宮一定走通
可以逆向思考，怎麼說呢，就是說。
假設現在咱們就在迷宮的出口，那麼你往回走（這個往回走，就是隨機產生的，可以任意一個方向），最後到達入口，那麼這么一個路線就一定可以走的通 呀。。。
Ⅲ java迷宮路徑總條數問題
int[][] data是你的迷宮數組，返回值是路徑總條數，不需要遞歸
public int findWayCount(int[][] data) {
int[][] way = new int[data.length][];
for (int m = 0; m < data.length; m++) {
way[m] = new int[data[m].length];
for (int n = 0; n < data[m].length; n++) {
if (data[m][n] == 0) {
way[m][n] = 0;
} else if (m == 0 && n == 0) {
way[m][n] = data[0][0];
} else if (m == 0) {
way[m][n] = way[m][n - 1];
} else if (n == 0) {
way[m][n] = way[m - 1][n];
} else {
way[m][n] = way[m][n - 1] + way[m - 1][n];
}
}
}
Ⅳ 急需一java高手幫忙寫一迷宮程序
給你代碼，你給出的那兩個類，不能滿足，我的需要，我就沒有使用。
你看一下吧。
----------------------------------------
package stackpackage;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Maze {
// 上
private static Point directionTop = new Point(-1, 0);
// 下
private static Point directionBottom = new Point(1, 0);
// 左
private static Point directionLeft = new Point(0, -1);
// 右
private static Point directionRight = new Point(0, 1);
private static Point[] directions = { directionTop, directionRight,
directionBottom, directionLeft };
private static boolean isStop = false;
private static int row = 0;
private static int col = 0;
private static Point startPoint = new Point();
public static void main(String[] args) throws Exception {
FileReader fr = new FileReader("data.txt");
BufferedReader br = new BufferedReader(fr);
int rowIndex = 1;
int[][] maze = null;
while (br.ready()) {
String line = br.readLine();
Scanner sc = new Scanner(line);
if (rowIndex == 1) {
row = sc.nextInt();
col = sc.nextInt();
maze = new int[row][col];
} else {
if (rowIndex < row + 2) {
for (int i = 0; i < col; i++) {
maze[rowIndex - 2][i] = sc.nextInt();
}
} else {
startPoint.x = sc.nextInt();
startPoint.y = sc.nextInt();
}
}
rowIndex++;
}
List<Point> route = new ArrayList<Point>();
route.add(startPoint);
findNext(startPoint);
puzzle(maze, startPoint, route);
System.out.println(route);
}
private static void puzzle(int[][] maze, Point p, List<Point> route) {
if (isStop) {
return;
}
Point[] nextDirections = p.nextDirections;
for (int i = 0; i < nextDirections.length; i++) {
if (isStop) {
return;
}
Point direction = nextDirections[i];
Point newP = new Point(p.x + direction.x, p.y + direction.y);
if (newP.isEffective() && maze[newP.x][newP.y] == 0
&& !route.contains(newP)) {
newP.before = p;
findNext(newP);
route.add(newP);
if (isExit(newP)) {
isStop = true;
break;
}
puzzle(maze, newP, route);
}
}
if (isStop) {
return;
}
route.remove(route.size() - 1);
}
private static void findNext(Point p) {
int index = 0;
Point[] nextDirections = new Point[3];
for (int i = 0; i < nextDirections.length; i++) {
nextDirections[i] = new Point(0, 0);
}
for (int i = 0; i < directions.length; i++) {
Point direction = directions[i];
Point newP = new Point(p.x + direction.x, p.y + direction.y);
if (newP.isEffective() && !newP.equals(p.before) && newP.x < row
&& newP.y < col) {
nextDirections[index++] = direction;
}
}
p.nextDirections = nextDirections;
}
private static boolean isExit(Point p) {
if (startPoint.equals(p)) {
return false;
}
for (int i = 0; i < directions.length; i++) {
Point direction = directions[i];
Point newP = new Point(p.x + direction.x, p.y + direction.y);
if (!newP.equals(p.before)
&& (newP.x >= row || newP.y >= col || newP.x < 0 || newP.y < 0)) {
return true;
}
}
return false;
}
}
class Point {
int x = 0;
int y = 0;
Point[] nextDirections = null;
Point before = null;
public Point() {
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public String toString() {
return "<" + x + "," + y + ">";
}
public boolean isEffective() {
return x >= 0 && y >= 0;
}
public boolean equals(Object obj) {
return equals((Point) obj);
}
public boolean equals(Point p) {
if (p == null) {
return false;
}
return this.x == p.x && this.y == p.y;
}
}
Ⅳ 急求大佬幫忙寫一下java程序
遞歸的話就是深度優先搜索（可以理解成不撞南牆不回頭，撞了牆就原路返回）可以加上剪枝（就是做標記，如果之前某一次走過但不通的路下次再走到就不用走了）
用棧的話應該是廣度優先搜索（大概就是分裂無數個你，每次向所有方向走一步），不過廣搜要用隊列實現，用棧本質還是深搜了
具體演算法可以搜網路
Ⅵ Java迷宮演算法問題（用棧實現）有演算法簡述
importjava.io.File;
importjava.io.FileNotFoundException;
importjava.util.HashSet;
importjava.util.LinkedList;
importjava.util.List;
importjava.util.Scanner;
publicclassTest{
publicstaticvoidmain(String[]args)throwsFileNotFoundException{
Scannerinput=newScanner(newFile("Maze2tong.txt"));
introw=0;
char[][]Mazemap=newchar[12][58];
while(input.hasNext()){
Stringline=input.nextLine();
for(intcolumn=0;column<=line.length()-1;column++){
charc=line.charAt(column);
Mazemap[row][column]=c;
}
row++;
}
for(inti=0;i<12;i++){
for(intj=0;j<58;j++){
System.out.print(Mazemap[i][j]);
}
System.out.print(" ");
}
LinkedList<TwoTuple<Integer,Integer>>trace=newLinkedList<TwoTuple<Integer,Integer>>();
System.out.println(maze(Mazemap,trace));
System.out.println(trace);
}
publicstaticbooleanmaze(char[][]maze,
List<TwoTuple<Integer,Integer>>trace){
LinkedList<TwoTuple<Integer,Integer>>path=newLinkedList<TwoTuple<Integer,Integer>>();
HashSet<TwoTuple<Integer,Integer>>traverse=newHashSet<TwoTuple<Integer,Integer>>();
for(inti=0;i<maze.length;i++){
for(intj=0;j<maze[i].length;j++){
if(maze[i][j]=='S'){
path.add(newTwoTuple<Integer,Integer>(i,j));
}
}
}
while(!path.isEmpty()){
TwoTuple<Integer,Integer>temp=path.pop();
if(traverse.contains(temp)){
continue;
}elseif(maze[temp.first][temp.second]=='F'){
trace.add(temp);
returntrue;
}elseif(!traverse.contains(temp)){
if(temp.second+1<maze[temp.first].length
&&maze[temp.first][temp.second+1]!='W')
path.add(newTwoTuple<Integer,Integer>(temp.first,
temp.second+1));
if(temp.second-1>0
&&maze[temp.first][temp.second-1]!='W')
path.add(newTwoTuple<Integer,Integer>(temp.first,
temp.second-1));
if(temp.first+1<maze.length
&&maze[temp.first+1][temp.second]!='W')
path.add(newTwoTuple<Integer,Integer>(temp.first+1,
temp.second));
if(temp.first-1>0
&&maze[temp.first-1][temp.second]!='W')
path.add(newTwoTuple<Integer,Integer>(temp.first-1,
temp.second));
traverse.add(temp);
trace.add(temp);
}
}
trace.clear();
returnfalse;
}
}
classTwoTuple<A,B>{
publicfinalAfirst;
publicfinalBsecond;
publicTwoTuple(Aa,Bb){
first=a;
second=b;
}
@Override
publicinthashCode(){
returnfirst.hashCode()+second.hashCode();
}
@Override
publicbooleanequals(Objectobj){
if(!(objinstanceofTwoTuple)){
}
returnobjinstanceofTwoTuple&&first.equals(((TwoTuple)obj).first)
&&second.equals(((TwoTuple)obj).second);
}
publicStringtoString(){
return"("+first+","+second+")";
}
}///:-
importjava.io.File;
importjava.io.FileNotFoundException;
importjava.util.LinkedList;
importjava.util.Scanner;
classMyPoint
{
publicbooleanvisited=false;
publicintparentRow=-1;
publicintparentColumn=-1;
publicfinalcharcontent;
publicintx;
publicinty;
publicMyPoint(charc,intx,inty)
{
this.content=c;
this.x=x;
this.y=y;
}
}
publicclassMaze
{
publicstaticMyPoint[][]getMazeArray(){
Scannerinput=null;
MyPoint[][]mazemap=newMyPoint[12][58];
try{
input=newScanner(newFile("Maze2tong.txt"));
introw=0;
while(input.hasNext()){
Stringline=input.nextLine();
for(intcolumn=0;column<=line.length()-1;column++){
charc=line.charAt(column);
MyPointpoint=newMyPoint(c,row,column);
mazemap[row][column]=point;
}
row++;
}
input.close();
}catch(FileNotFoundExceptione){
e.printStackTrace();
}
returnmazemap;
}
publicstaticbooleantomRun(MyPoint[][]maze,MyPointend)
{
intx=maze.length;
inty=maze[0].length;
LinkedList<MyPoint>stack=newLinkedList<MyPoint>();
for(inti=0;i<maze.length;i++){
for(intj=0;j<maze[i].length;j++){
if(maze[i][j].content=='S'){
stack.push(maze[i][j]);
maze[i][j].visited=true;
}
}
}
booleanresult=false;
while(!stack.isEmpty())
{
MyPointt=stack.pop();
//System.out.println("poppoint:"+t.x+""+t.y+"value:"+maze[t.x][t.y]);
if(t.content=='F')
{
result=true;
end.x=t.x;
end.y=t.y;
break;
}
if(t.x-1>0&&maze[t.x-1][t.y].visited==false&&maze[t.x-1][t.y].content!='W')
{
stack.push(maze[t.x-1][t.y]);
maze[t.x-1][t.y].parentRow=t.x;
maze[t.x-1][t.y].parentColumn=t.y;
maze[t.x-1][t.y].visited=true;
}
if(t.x+1<x&&maze[t.x+1][t.y].visited==false&&maze[t.x+1][t.y].content!='W')
{
stack.push(maze[t.x+1][t.y]);
maze[t.x+1][t.y].parentRow=t.x;
maze[t.x+1][t.y].parentColumn=t.y;
maze[t.x+1][t.y].visited=true;
}
if(t.y-1>0&&maze[t.x][t.y-1].visited==false&&maze[t.x][t.y-1].content!='W')
{
stack.push(maze[t.x][t.y-1]);
maze[t.x][t.y-1].parentRow=t.x;
maze[t.x][t.y-1].parentColumn=t.y;
maze[t.x][t.y-1].visited=true;
}
if(t.y+1<y&&maze[t.x][t.y+1].visited==false&&maze[t.x][t.y+1].content!='W')
{
stack.push(maze[t.x][t.y+1]);
maze[t.x][t.y+1].parentRow=t.x;
maze[t.x][t.y+1].parentColumn=t.y;
maze[t.x][t.y+1].visited=true;
}
}
returnresult;
}
publicstaticvoidshow(intx,inty,MyPoint[][]visited)
{
if(visited[x][y].parentRow==-1)
{
System.out.println("["+x+","+y+"]");
return;
}
show(visited[x][y].parentRow,visited[x][y].parentColumn,visited);
System.out.println("->"+"["+x+","+y+"]");
}
publicstaticvoidmain(String[]args)
{
MyPoint[][]maze=getMazeArray();
MyPointpoint=newMyPoint('c',1,1);
if(tomRun(maze,point))
{
System.out.println("逃生路徑如下：");
show(point.x,point.y,maze);
}
else
System.out.println("無法走出迷宮！");
}
}
Ⅶ 用java語言控制小機器人走迷宮的演算法
我昨天剛寫了個走迷宮的界面(一個初始小球，一個目標小球，隨機在界面種生成障礙(迷宮圖)，然後初始小球移動到目標小球那)，不知道是否跟你的想法一樣。用的是回溯法(目前我只知道這個演算法走迷宮)，你可以查下。PS:我電腦沒聯網不能把代碼給你…QQ254774042。
Ⅷ 請幫忙用數據結構（java版）的知識解決這道迷宮問題的程序代碼。
我這是用c寫的。你可以看看，希望能幫助到你。
#include"stdlib.h"
#include"stdio.h"
#define N 50
#define M 50
int X;
int maze[N+2][M+2];
struct point{
int row,col,predecessor;
}queue[512];
int head=0,tail=0;
void shoudong_maze(int m,int n){
int i,j;
printf("\n\n");
printf("請按行輸入迷宮，0表示通路，1表示障礙:\n\n");
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&maze[i][j]);
}
void zidong_maze(int m,int n){
int i,j;
printf("\n迷宮生成中……\n\n");
system("pause");
for(i=0;i<m;i++)
for(j=0;j<n;j++)
maze[i][j]=rand()%2;
//由於rand()產生的隨機數是從0到RAND_MAX
//RAND_MAX是定義在stdlib.h中的,其值至少為32767)
//要產生從X到Y的數,只需要這樣寫：k=rand()%(Y-X+1)+X;
}
void print_maze(int m,int n){
int i,j;
printf("\n迷宮生成結果如下:\n\n");
printf("迷宮入口\n");
printf("↓");
for(i=0;i<m;i++)
{printf("\n");
for(j=0;j<n;j++)
{if(maze[i][j]==0) printf("□");
if(maze[i][j]==1) printf("■");}
}
printf("→迷宮出口\n");
}
void result_maze(int m,int n)
{ int i,j;
printf("迷宮通路(用☆表示)如下所示：\n\t");
for(i=0;i<m;i++)
{ printf("\n");
for(j=0;j<n;j++)
{if(maze[i][j]==0||maze[i][j]==2) printf("□");
if(maze[i][j]==1) printf("■");
if(maze[i][j]==3) printf("☆");
}
}
}
void enqueue(struct point p)
{ queue[tail]=p;
tail++;
}
struct point dequeue()
{ head++;
return queue[head-1];
}
int is_empty()
{ return head==tail;
}
void visit(int row,int col,int maze[52][52])
{ struct point visit_point={row,col,head-1};
maze[row][col]=2;
enqueue(visit_point);
}
int mgpath(int maze[52][52],int m,int n)
{ X=1;
struct point p={0,0,-1};
if(maze[p.row][p.col]==1)
{ printf("\n===============================================\n");
printf("此迷宮無解\n\n");X=0;return 0;}
maze[p.row][p.col]=2;
enqueue(p);
while(!is_empty())
{p=dequeue();
if((p.row==m-1)&&(p.col==n-1)) break;
if((p.col+1<n)&&(maze[p.row][p.col+1]==0)) visit(p.row,p.col+1,maze);
if((p.row+1<m)&&(maze[p.row+1][p.col]==0)) visit(p.row+1,p.col,maze);
if((p.col-1>=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze);
if((p.row-1>=0)&&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze);
}
if(p.row==m-1&&p.col==n-1)
{printf("\n==================================================================\n");
printf("迷宮路徑為：\n");
printf("(%d,%d)\n",p.row,p.col);
maze[p.row][p.col]=3;
while(p.predecessor!=-1)
{p=queue[p.predecessor];
printf("(%d,%d)\n",p.row,p.col);
maze[p.row][p.col]=3;
}
}
else {printf("\n=============================================================\n");
printf("此迷宮無解！\n\n");X=0;}
return 0;
}
int main()
{int i,m,n,cycle=0;
while(cycle!=(-1))
{
printf("********************************************************************************\n");
printf(" ☆歡迎進入迷宮求解系統☆\n");
printf(" 設計者:尹旭 林靜波（信息2班）\n");
printf("********************************************************************************\n");
printf(" 手動生成迷宮 請按：1\n");
printf(" 自動生成迷宮 請按：2\n");
printf(" 退出 請按：3\n\n");
printf("********************************************************************************\n");
printf("\n");
printf("請選擇你的操作：\n");
scanf("%d",&i);
switch(i)
{case 1:printf("\n請輸入行數：");
scanf("%d",&m);
printf("\n");
printf("請輸入列數：");
scanf("%d",&n);
while((m<=0||m>50)||(n<=0||n>50))
{ printf("\n抱歉，你輸入的行列數超出預設范圍(0-50,0-50),請重新輸入：\n\n");
printf("請輸入行數：");
scanf("%d",&m);
printf("\n");
printf("請輸入列數：");
scanf("%d",&n);
}
shoudong_maze(m,n);
print_maze(m,n);
mgpath(maze,m,n);
if(X!=0)
result_maze(m,n);
printf("\n\nPress Enter Contiue!\n");
getchar();
while(getchar()!='\n');
break;
case 2:printf("\n請輸入行數：");
scanf("%d",&m);
printf("\n");
printf("請輸入列數：");
scanf("%d",&n);
while((m<=0||m>50)||(n<=0||n>50))
{printf("\n抱歉，你輸入的行列數超出預設范圍(0-50,0-50),請重新輸入：\n\n");
printf("請輸入行數：");
scanf("%d",&m);
printf("\n");
printf("請輸入列數：");
scanf("%d",&n);
}
zidong_maze(m,n);
print_maze(m,n);
mgpath(maze,m,n);
if(X!=0)
result_maze(m,n);
printf("\n\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;
case 3:cycle=(-1);
break;
default:printf("\n");
printf("你的輸入有誤!\n");
printf("\nPress Enter Contiue!\n");
getchar();
while(getchar()!='\n');break;
}
}
}
Ⅸ 幫忙給個迷宮問題的JAVA程序，最好是用VC..粘的也好，只要可以運行就好..
import java.io.*;
import java.util.Stack;
class MazeCell {
int x, y;
MazeCell() {
}
MazeCell(int i, int j) {
x = i; y = j;
}
boolean equals(MazeCell cell) {
return x == cell.x && y == cell.y;
}
}
class Maze {
int rows = 0, cols = 0;
char[][] store;
MazeCell currentCell, exitCell = new MazeCell(), entryCell = new MazeCell();
final char exitMarker = 'e', entryMarker = 'm', visited = '.';
final char passage = '0', wall = '1';
Stack mazeStack = new Stack();
Maze() {
int row = 0, col = 0;
Stack mazeRows = new Stack();
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader buffer = new BufferedReader(isr);
String str;
System.out.println("Enter a rectangular maze using the following "
+ "characters:\nm - entry\ne - exit\n1 - wall\n0 - passage\n"
+ "Enter one line at at time; end with Ctrl-z (PC) or Ctrl-D (Unix):");
try {
str = buffer.readLine();
while (str != null) {
row++;
cols = str.length();
str = "1" + str + "1"; // put 1s in the borderline cells;
mazeRows.push(str);
if (str.indexOf(exitMarker) != -1) {
exitCell.x = row;
exitCell.y = str.indexOf(exitMarker);
}
if (str.indexOf(entryMarker) != -1) {
entryCell.x = row;
entryCell.y = str.indexOf(entryMarker);
}
str = buffer.readLine();
}
} catch(IOException eof) {
}
rows = row;
store = new char[rows+2][]; // create a 1D array of char arrays;
store[0] = new char[cols+2]; // a borderline row;
for ( ; !mazeRows.isEmpty(); row--)
store[row] = ((String) mazeRows.pop()).toCharArray();
store[rows+1] = new char[cols+2]; // another borderline row;
for (col = 0; col <= cols+1; col++) {
store[0][col] = wall; // fill the borderline rows with 1s;
store[rows+1][col] = wall;
}
}
void display(PrintStream out) {
for (int row = 0; row <= rows+1; row++)
out.println(store[row]);
out.println();
}
void pushUnvisited(int row, int col) {
if (store[row][col] == passage || store[row][col] == exitMarker)
mazeStack.push(new MazeCell(row,col));
}
void exitMaze(PrintStream out) {
int row = 0, col = 0;
currentCell = entryCell;
out.println();
while (!currentCell.equals(exitCell)) {
row = currentCell.x;
col = currentCell.y;
display(System.out); // print a snapshot;
if (!currentCell.equals(entryCell))
store[row][col] = visited;
pushUnvisited(row-1,col);
pushUnvisited(row+1,col);
pushUnvisited(row,col-1);
pushUnvisited(row,col+1);
if (mazeStack.isEmpty()) {
display(out);
out.println("Failure");
return;
}
else currentCell = (MazeCell) mazeStack.pop();
}
display(out);
out.println("Success");
}
static public void main (String args[]) {
(new Maze()).exitMaze(System.out);
}
}
試一下這個，是不是你想要的……
___________________________________________________________________________________________________________________________
html代碼？你是說你要做一個java applet的網頁迷宮小游戲？？
Ⅹ 求用java語言尋找走出迷宮路線的演算法
首先給定一個初始坐標，然後構建一個容器保存坐標值，之後進行迭代，橫坐標+1，或者縱坐標+1，這個順尋自己定義（四個方向），經過的「路徑」保存在那個容器中，如果遇到死角，以此往回迭代，在容器中將遇到死角的那個坐標刪除。最後找到自己定義的那個迷宮出口坐標。