迷宫问题
time limit per test 1 second memory limit per test 256 megabytes
定义一个二维数组:
int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。

传送门:POJ3964

Input

一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径,格式如样例所示。

Sample Input

1
2
3
4
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

1
2
3
4
5
6
7
8
9
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

题解

简单bfs 主要有一点注意 在回溯路径时两个变量要预先存一下 否则一个改了会影响下一个(自言自语) ## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.*;  
import java.util.*;
public class Main {
static int[][]maze;
static boolean[][]used;
static Node[][]pre;
static int[]dx={1,-1,0,0};
static int[]dy={0,0,1,-1};
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
maze=new int[5][5];
used=new boolean[5][5];
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
maze[i][j]=sc.nextInt();
}
}
pre=new Node[5][5];
bfs();
int x=4;
int y=4;
ArrayList<String>list=new ArrayList<String>();
while(!(x==0&&y==0)){
list.add("("+x+", "+y+")");
//fatal problem
int ti=pre[x][y].i;
int tj=pre[x][y].j;
x=ti;
y=tj;
}
list.add("("+0+", "+0+")");
for(int i=list.size()-1;i>=0;i--){
pw.println(list.get(i));
}
pw.flush();
}

}
static void bfs(){
Queue<Node>queue=new LinkedList<Node>();
queue.add(new Node(0,0));
used[0][0]=true;
while(!queue.isEmpty()){
Node t=queue.poll();
if(t.i==4&&t.j==4){
break;
}else{
for(int i=0;i<4;i++){
int tx=t.i+dx[i];
int ty=t.j+dy[i];
if(check(tx,ty)&&!used[tx][ty]){
queue.add(new Node(tx,ty));
pre[tx][ty]=new Node(t.i,t.j);
used[tx][ty]=true;
}
}
}
}
}
static boolean check(int x,int y){
if(x<0||x>=5||y<0||y>=5)return false;
if(maze[x][y]==1)return false;
return true;
}
}
class Node{
int i;
int j;
Node(int a,int b){
i=a;
j=b;
}
}