迷宫问题
1
2
3
4 /*************************************************************************
5 > File Name: code/2015summer/searching/KK.cpp
6 > Author: 111qqz
7 > Email: rkz2013@126.com
8 > Created Time: 2015年07月25日 星期六 13时33分00秒
9 ************************************************************************/
10
11 #include<iostream>
12 #include<iomanip>
13 #include<cstdio>
14 #include<algorithm>
15 #include<cmath>
16 #include<cstring>
17 #include<string>
18 #include<map>
19 #include<set>
20 #include<queue>
21 #include<vector>
22 #include<stack>
23 #define y0 abc111qqz
24 #define y1 hust111qqz
25 #define yn hez111qqz
26 #define j1 cute111qqz
27 #define tm crazy111qqz
28 #define lr dying111qqz
29 using namespace std;
30 #define REP(i, n) for (int i=0;i<int(n);++i)
31 typedef long long LL;
32 typedef unsigned long long ULL;
33 int a[10][10];
34 int head = 0;
35 int tail = 1;
36 int dirx[2]={1,0};
37 int diry[2]={0,1};
38 struct node
39 {
40 int x,y,pre;
41 }q[10];
42
43 void print(int x)
44 {
45 if (q[x].pre!=-1)
46 {
47 print(q[x].pre);
48 printf("(%d, %d)\n",q[x].x,q[x].y);
49 }
50 }
51 void bfs()
52 {
53 q[head].x=0;
54 q[head].y=0;
55 q[head].pre=-1;
56 while (head<tail)
57 {
58 if (q[head].x==4&&q[head].y==4)
59 {
60 print(head);
61 return;
62 }
63 for (int i = 0 ; i < 2 ; i++ )
64 {
65 int newx=dirx[i]+q[head].x;
66 int newy=diry[i]+q[head].y;
67 if (newx>=0&&newx<5&&newy>=0&&newy<5&&a[newx][newy]==0)
68 {
69 q[tail].x=newx;
70 q[tail].y=newy;
71 q[tail].pre=head;
72 tail++;
73 }
74 }
75 head++;
76 }
77
78 }
79 int main()
80 {
81 for ( int i = 0 ; i < 5 ; i++ )
82 {
83 for ( int j = 0 ; j < 5; j++)
84 {
85 cin>>a[i][j];
86 }
87 }
88 printf("(0, 0)\n");
89 bfs();
90
91 return 0;
92 }