Poj-3984-迷宫问题 (Bfs 路径）

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 32323 Accepted: 18471

1 Description

``````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,
};
``````

4 Sample Input

``````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
``````

5 Sample Output

``````(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
``````

6 题解

 `````` 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 `````` ``````#include #include using namespace std; int map[5][5]; int visited[5][5]; int dx[4]={0, 1, 0, -1}; int dy[4]={ 1, 0,-1, 0}; int head,tail; struct node{ int xx,yy; int fa;//父节点 }pre[25],way[25]; void BFS(int x,int y) { int x1,y1; visited[x][y]=1; pre[0].xx=x,pre[0].yy=y; while(tail>head)//栈空 { x=pre[head].xx; y=pre[head].yy; if(x==4&&y==4)//结束标志 return ; for(int i=0;i<4;i++) { x1=x+dx[i];y1=y+dy[i]; if(x1>=0&&x1<=4&&y1>=0&&y1<=4) if(map[x1][y1]==0&&!visited[x1][y1]) { pre[tail].xx=x1; pre[tail].yy=y1; pre[tail].fa=head; visited[x1][y1]=1; tail+=1;//入栈 } } head++;//相当于出栈 } } int main() { int i,j; ios::sync_with_stdio(false); memset(map,0,sizeof(map)); memset(visited,0,sizeof(visited)); for(i=0;i<5;i++) for(j=0;j<5;j++) cin>>map[i][j]; BFS(0,0); i=0; while(head)//逆序进行赋值输出就是通路 { way[i].xx=pre[head].xx; way[i].yy=pre[head].yy; head=pre[head].fa; i++; } //画一下队列 way[i].xx=0;way[i].yy=0; while(i!=-1) { cout<<"("<