DFS的联通块问题（模板）
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn=1000;
4 int n,m;
5 //地图尺寸
6 int maap[maxn+10][maxn+10];
7 //查找零一地图中的1联通块个数
8 bool vis[maxn+10][maxn+10];
9 int direx[]={1,-1,0,0};
10 int direy[]={0,0,1,-1};
11 //四向联通
12 void dfs(int x,int y)
13 {
14 vis[x][y]=true;
15 //打访问标记
16 for(int i=0;i<4;i++)
17 {
18 int x_now=x+direx[i];
19 int y_now=y+direy[i];
20 if(x_now>=1&&x_now<=n&&y_now>=1&&y_now<=m&&!vis[x_now][y_now]&&maap[x_now][y_now]==1)
21 //不超边界未访问不为0
22 {
23 dfs(x_now,y_now);
24 }
25 }
26 }
27 int main()
28 {
29 int cnt=0;
30 cin>>n>>m;
31 for(int i=1;i<=n;i++)
32 {
33 for(int j=1;j<=m;j++)
34 {
35 cin>>maap[i][j];
36 }
37 }//输入
38 for(int i=1;i<=n;i++)
39 {
40 for(int j=1;j<=m;j++)
41 {
42 if(maap[i][j]==1&&!vis[i][j])
43 {
44 dfs(i,j);
45 cnt++;
46 }
47 }
48 }//dfs计数模块，不能把它直接加在输入环节！！
49 //不然地图都没输入完求个啥的联块！！
50 cout<<cnt<<endl;
51 }
DFS的计步（最短路）问题（模板）
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn=1000;
4 int maap[maxn+10][maxn+10];
5 //零一迷宫的最短路问题(不剪枝优化)
6 //0是障碍,1是道路
7 bool vis[maxn+10][maxn+10];
8 //访问标记
9 int direx[]={0,1,0,-1};
10 int direy[]={1,0,-1,0};
11 //四向联通
12 int n,m;
13 //地图尺寸
14 int stx,sty,edx,edy;
15 //起点终点坐标
16 int minstep;
17 //最少步数(初始化为矩阵内遍历步数)
18 void dfs(int x, int y, int step)
19 {
20 vis[x][y] = true;
21 //打访问标记
22 if(x == edx && y == edy)
23 //到达终点
24 {
25 minstep=min(minstep,step);
26 //打擂台
27 return;
28 }
29 for(int i = 0; i < 4; i++)
30 {
31 int x_now = x + direx[i];
32 int y_now = y + direy[i];
33 if(1<=x_now&&x_now<=n&&1<=y_now&&y_now<=m&&vis[x_now][y_now]==0&&maap[x_now][y_now])
34 //不出界未访问不撞墙判定
35 {
36 dfs(x_now, y_now, step+1);
37 }
38 }
39 vis[x][y] = false;//回溯
40 }
41 int main()
42 {
43 cin>>n>>m;
44 minstep=n*m;
45 for(int i=1;i<=n;i++)
46 {
47 for(int j=1;j<=m;j++)
48 {
49 cin>>maap[i][j];
50 }
51 }
52 cin>>stx>>sty>>edx>>edy;//输入
53 dfs(stx,sty,0);
54 //深搜
55 cout<<minstep<<endl;
56 return 0;
57 }
DFS剪枝优化计步（模板）
1 void dfs(int x, int y, int step)
2 {
3 /************唯一的变化*************/
4 if(step>minstep)
5 {
6 return;
7 }
8 /**********************************/
9 vis[x][y] = true;
10 //打访问标记
11 if(x == edx && y == edy)
12 //到达终点
13 {
14 minstep=min(minstep,step);
15 //打擂台
16 return;
17 }
18 for(int i = 0; i < 4; i++)
19 {
20 int x_now = x + direx[i];
21 int y_now = y + direy[i];
22 if(1<=x_now&&x_now<=n&&1<=y_now&&y_now<=m&&vis[x_now][y_now]==0&&maap[x_now][y_now])
23 //不出界未访问不撞墙判定
24 {
25 dfs(x_now, y_now, step+1);
26 }
27 }
28 vis[x][y] = false;//回溯
29 }