BFS()DFS()テンプレート
14564 ワード
1 /*
2 2D BFS ， STL
3 */
4
5 #include<cstdio>
6 #include<cstring>
7 #include<queue>
8 #include<algorithm>
9 using namespace std;
10
11 const int maxn=100;
12
13 bool vst[maxn][maxn]; //
14
15 int dir[4][2]={0,1,0,-1,1,0,-1,0}; //
16 struct State // BFS
17 {
18 int x,y; //
19 int Step_Counter; //
20 };
21 State a[maxn];
22
23 bool CheckState(State s) //
24 {
25 if(!vst[s.x][s.y] && ...) //
26 return 1;
27 else //
28 return 0;
29 }
30
31 void bfs(State st)
32 {
33 queue <State> q; // BFS
34 State now,next; // 2 ，
35 st.Step_Counter=0; //
36 q.push(st); //
37 vst[st.x][st.y]=1; //
38 while(!q.empty())
39 {
40 now=q.front(); //
41 if(now==G) // ， Step_Counter ，
42 {
43 ...... //
44 return;
45 }
46 for(int i=0;i<4;i++)
47 {
48 next.x=now.x+dir[i][0]; //
49 next.y=now.y+dir[i][1];
50 next.Step_Counter=now.Step_Counter+1; // 1
51 if(CheckState(next)) //
52 {
53 q.push(next);
54 vst[next.x][next.y]=1; //
55 }
56 }
57 q.pop(); //
58 }
59 return;
60 }
61
62 int main()
63 {
64 ......
65 return 0;
66 } 1 /*
2 DFS 2D ， DFS 。
3 */
4
5 #include<cstdio>
6 #include<cstring>
7 #include<cstdlib>
8 using namespace std;
9
10 const int maxn=100;
11
12 bool vst[maxn][maxn]; //
13
14 int map[maxn][maxn]; //
15 int dir[4][2]={0,1,0,-1,1,0,-1,0}; // ，(x,y)
16
17 bool CheckEdge(int x,int y) //
18 {
19 if(!vst[x][y] && ...) //
20 return 1;
21 else //
22 return 0;
23 }
24
25 void dfs(int x,int y)
26 {
27 vst[x][y]=1; //
28 if(map[x][y]==G) // G
29 {
30 ...... //
31 return;
32 }
33 for(int i=0;i<4;i++)
34 {
35 if(CheckEdge(x+dir[i][0],y+dir[i][1])) //
36 dfs(x+dir[i][0],y+dir[i][1]);
37 }
38 return; // ，
39 }
40
41 int main()
42 {
43 ......
44 return 0;
45 }