刚学搜索,总是不开窍,看了介绍,自己磨了两小时才写出来。后面会有DFS和改进后的方法。想通过这道水题,把搜索入了门先。
蓝桥大赛还有几天,再看看,自己水死了。
自己的代码: 1 #include<iostream>
2 #include<queue>
3 #include<stack>
4 using namespace std;
5 //===================================================================
6 int maze[5][5];
7 bool mark[5][5];
8 struct Point
9 {
10 int x,y;
11 };
12
13 int dir[4][2]={0,1,0,-1,1,0,-1,0};
14 Point dis[5][5];
15 stack<Point> S;
16 int map[5][5];
17 //=====================================================================
18
19 bool InMap(int i,int j)
20 {
21 if(i>=0&& i<=4 && j>=0 && j<=4) return true;
22 else return false;
23 }
24
25 void func(int i, int j)
26 {
27 if(i==0 && j==0)
28 {
29 printf("(0, 0)\n");
30 return ;
31 }
32 Point t;
33 t.x=i;
34 t.y=j;
35 S.push(t);
36 func(dis[i][j].x,dis[i][j].y); //递归放入栈,不知道怎么倒序输出
37
38 }
39
40 void BFS()
41 {
42 queue<Point> Q;
43
44 Point cur,m,q;
45 cur.x=0;
46 cur.y=0;
47 mark[0][0]=1;
48 Q.push(cur);
49 dis[0][0].x=0;
50 dis[0][0].y=0;
51 int xt,yt;
52
53 while(!Q.empty())
54 {
55 m=Q.front();
56 Q.pop();
57
58 for(int i=0;i<4;i++)
59 {
60 xt=m.x+dir[i][0];
61 yt=m.y+dir[i][1];
62 if(xt==4 && yt==4)
63 {
64 func(m.x,m.y);//放入栈
65 return ;
66 }
67 if(InMap(xt,yt) && mark[xt][yt]==0 && maze[xt][yt]==0)//判断下面一层的结点是否符合
68 {
69
70 dis[xt][yt].x=m.x;//记录每上次的结点,这样才可以把整个拎起来
71 dis[xt][yt].y=m.y;//用dis[][]点来记录每个节点的父节点,因为遍历过就会mark=1,所以只会有一个父节,不会被覆盖
72 mark[xt][yt]=1;//访问过后
73 q.x=xt;
74 q.y=yt;
75 Q.push(q);
76
77 }
78 }
79 }
80 }
81
82 int main()
83 {
84 int i,j;
85
86 //freopen("in.txt","r",stdin);
87 for(i=0;i<5;i++)
88 for(j=0;j<5;j++)
89 scanf("%d",&maze[i][j]);
90
91 BFS();
92
93 while(!S.empty())//打印路径
94 {
95 printf("(%d, %d)\n",S.top().x,S.top().y);
96 S.pop();
97 }
98 printf("(4, 4)\n");
99
100
101
102
103
104
105 }