1 #include<cstdio>
2 #include<iostream>
3 #include<queue>
4
5 using namespace std;
6
7 struct node{
8 int x, y;
9 int s;//路径长度
10 int l[50];//每次决策
11 };
12
13 int g[10][10], vis[10][10];
14 int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
15
16 inline node bfs(){
17 queue<node> q;
18 node now, next;
19 now.x = 0;
20 now.y = 0;
21 now.s = 0;
22 vis[0][0] = 1;
23 q.push(now);
24 while(!q.empty()){
25 now = q.front();
26 q.pop();
27 if(now.x == 4 && now.y == 4) return now;
28 for(int i = 0; i < 4; i++){
29 next.x = now.x + dir[i][0];
30 next.y = now.y + dir[i][1];
31 if(next.x >= 0 && next.x <= 4 && next.y >= 0 && next.y <= 4 && !g[next.x][next.y] && !vis[next.x][next.y]){
32 next.s = now.s + 1;
33 next.l[now.s] = i;
34 vis[next.x][next.y] = 1;
35 q.push(next);
36 }
37 }
38 }
39 return now;
40 }
41
42 int main(){
43 for(int i = 0; i < 5; i++){
44 for(int j = 0; j < 5; j++){
45 scanf("%d", &g[i][j]);
46 }
47 }
48 node ans = bfs();
49 int x = 0, y = 0;
50 printf("(0, 0)
");
51 for(int i = 0; i < ans.s; i++){
52 x += dir[ans.l[i]][0];
53 y += dir[ans.l[i]][1];
54 printf("(%d, %d)
", x, y);
55 }//根据记录的决策输出
56 return 0;
57 }
