本文主要是介绍图论第二章图的遍历与活动网络问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
图的遍历 搜索
2.1 DFS遍历
ZOJ 2110 骨头的诱惑
类似于走迷宫问题 从狗的位置在限定步骤内走到骨头的位置 其中有'X'作为墙壁 不能走
dfs()之前要将当前位置设为'X' 之后要恢复现场 设为'.'
程序中有用到剪枝的思想！！！
代码如下：
#include <iostream>
#include <cstdio>
#include <cmath>using namespace std;char map[9][9];
int di,dj;
int n,m,t;
bool escape;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};void dfs(int si,int sj,int cnt)
{int i,temp;if(si>n||sj>m||si<=0||sj<=0) return;if(si==di&&sj==dj&&t==cnt){escape=1;return;}temp=(t-cnt)-fabs(si-di)-fabs(sj-dj);if(temp<0||temp%2) return;for(i=0;i<4;i++){if(map[si+dir[i][0]][sj+dir[i][1]]!='X'){map[si+dir[i][0]][sj+dir[i][1]]='X';dfs(si+dir[i][0],sj+dir[i][1],cnt+1);if(escape) return;map[si+dir[i][0]][sj+dir[i][1]]='.';}}return;
}int main()
{int si,sj;while(scanf("%d%d%d",&n,&m,&t)!=EOF){if(n==0&&m==0&&t==0) break;int wall=0;char temp;scanf("%c",&temp);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%c",&map[i][j]);if(map[i][j]=='S') {si=i;sj=j;}else if(map[i][j]=='D') {di=i;dj=j;}else if(map[i][j]=='X') wall++;}scanf("%c",&temp);}if(n*m-wall<=t){puts("NO");continue;}escape=0;map[si][sj]='X';dfs(si,sj,0);if(escape) puts("YES");else puts("NO");}return 0;
}//AC一个有问题的代码 运行事例答案不对，贴出来 里面有注释：
#include <iostream>
#include <cstdio>
#include <cmath>using namespace std;char map[9][9];
int n,m,t;
int di,dj; //门的位置
bool escape; //是否成功逃脱
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};//分别表示下，上，左，右void dfs(int si,int sj,int cnt)
{int i,temp;if(si>n||sj<m||si<=0||sj<=0) return;if(si==di&&sj==dj&&cnt==t){escape=1;return;}
//abs(x-ex)+abs(y-ey)表示现在所在格子到目标格子的距离
//t-cnt是实际还需要的步数
//如果temp<0或者temp为奇数 那就不可能到达temp=(t-cnt)-fabs(si-di)-fabs(sj-dj);//搜索过程中的剪枝if(temp<0||temp%2) return;for(i=0;i<4;i++){if(map[si+dir[i][0]][sj+dir[i][1]]!='X'){//前进方向 将当前方格设置为墙壁'X'map[si+dir[i][0]][sj+dir[i][1]]='X';dfs(si+dir[i][0],sj+dir[i][1],cnt+1);if(escape) return;map[si+dir[i][0]][sj+dir[i][1]]='.';//后退方向 恢复现场}}return;
}int main()
{int si,sj;while(scanf("%d%d%d",&n,&m,&t)!=EOF){if(n==0&&m==0&&t==0) break;int wall=0;char temp;scanf("%c",&temp);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%c",&map[i][j]);if(map[i][j]=='S') {si=i;sj=j;}else if(map[i][j]=='D') {di=i;dj=j;}else if(map[i][j]=='X') wall++;}scanf("%c",&temp);}if(n*m-wall<=t){puts("NO");//cout<<1<<endl;continue;}escape=0;map[si][sj]='X';dfs(si,sj,0);
// cout<<escape<<endl;if(escape) puts("YES");else puts("NO");}return 0;
}
POJ 1562 油田 Oil Deposits
'@'表示一块油田 '*'表示没有油田 油田连在一起的视为一块油田 相连的方式有对角线 水平 垂直
所以对一个点搜索有八个方向 这个与上题的区别就是遍历'@'点之后把这点设为'*'且遍历完之后不要恢复现场
做这种题目遍历的时候要注意边界的判断
代码如下：
#include <iostream>
#include <cstdio>using namespace std;char grid[101][101];
int m,n;
int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};//八个方向void dfs(int x,int y)
{int xx,yy;grid[x][y]='*';for(int i=0;i<8;i++){xx=x+dir[i][0];yy=y+dir[i][1];if(xx<0||y<0||xx>=m||y>=n) continue;if(grid[xx][yy]=='@')dfs(xx,yy);}
}int main()
{while(scanf("%d%d",&m,&n)!=EOF){//getchar();if(m==0) break;for(int i=0;i<m;i++)scanf("%s",grid[i]);int count=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='@'){dfs(i,j);count++;}}}printf("%d\n",count);}return 0;
}ZOJ2412 农田灌溉
管道问题 其实这题跟上题类似 就是看有多少块是相连的 只要管道口是相连的就可以
首先要将管道口的方向合理转化 顺时针方向 上右下左依次 定义一个数组 1表示该方向有管道 0表示没有
还要注意深搜的条件判断 给一个vis 数组 用来判断这个点有木有被访问过
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;int m,n;
int map[55][55];
bool vis[55][55];
int dir[11][4]={{1,0,0,1},{1,1,0,0},{0,0,1,1},{0,1,1,0},{1,0,1,0},{0,1,0,1},{1,1,0,1},{1,0,1,1},{0,1,1,1},{1,1,1,0},{1,1,1,1}};void dfs(int x,int y)
{vis[x][y]=1;for(int z=0;z<4;z++){if(z==0&&dir[map[x][y]][z]&&x>=1&&dir[map[x-1][y]][2]&&!vis[x-1][y]) dfs(x-1,y);else if(z==1&&dir[map[x][y]][z]&&y<=n-2&&dir[map[x][y+1]][3]&&!vis[x][y+1]) dfs(x,y+1);else if(z==2&&dir[map[x][y]][z]&&x+1<m&&dir[map[x+1][y]][0]&&!vis[x+1][y]) dfs(x+1,y);else if(z==3&&dir[map[x][y]][z]&&y-1>=0&&dir[map[x][y-1]][1]&&!vis[x][y-1]) dfs(x,y-1);}
}int main()
{while(scanf("%d%d",&m,&n)!=EOF){if(m<0||n<0) break;memset(map,0,sizeof(map));char ch[55];for(int i=0;i<m;i++){scanf("%s",ch);for(int j=0;j<n;j++){map[i][j]=ch[j]-'A';}}memset(vis,0,sizeof(vis));int count=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(vis[i][j]) continue;dfs(i,j);count++;}}printf("%d\n",count);}return 0;
}zoj 1008 Gnoma Tetravex
题目大意 就是移动正方形 使得左右相邻的数字相等 上下相邻的数字相等
注意这里面可能会有一模一样的正方形
照着别人的思路写的代码 老是WA 不知道什么情况 贴个代码：
#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;struct node
{int top,rig,bot,lef;int num;
};node no[25],map[5][5];
int n,kinds;
bool suc;void dfs(int x)
{if(x==n*n){suc=1;return;}if(suc) return;for(int i=0;i<kinds;i++){if(no[i].num&&(x%n==0||no[i].lef==map[x/n][x%n-1].rig)&&(x/n==0||no[i].top==map[x/n-1][x%n].bot)){map[x/n][x%n]=no[i];no[i].num--;dfs(x+1);no[i].num++;}}
}int main()
{node temp;int count=0;while(scanf("%d",&n)!=EOF){if(n==0) break;kinds=0;for(int i=0;i<n*n;i++){scanf("%d%d%d%d",&temp.top,&temp.rig,&temp.bot,&temp.lef);temp.num=1;bool flag=1;for(int j=0;j<kinds;j++){if(temp.top==no[j].top&&temp.rig==no[j].rig&&temp.bot==no[j].bot&&temp.lef==no[j].lef){flag=0;no[j].num++;break;}}if(flag){no[kinds++]=temp;}}suc=0;dfs(0);if(count) puts("");if(suc) printf("Game %d:Possible\n",++count);else printf("Game %d:Impossible\n",++count);}return 0;
}
ZOJ 2165 Red And Black
题目大意：类似于迷宫问题 就是‘.’表示黑色砖块 可以走的 '#'表示红色砖块 不可以走的
'@'为人初始的位置 计算能走的砖块的个数
代码如下：比较简单
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;char map[20][20];
int si,sj;
bool vis[20][20];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int count;
int w,h;void dfs(int x,int y)
{count++;map[x][y]='#';for(int i=0;i<4;i++){int m=dir[i][0]+x,n=y+dir[i][1];if(m<0||n<0||m>=h||n>=w) continue;else{if(map[m][n]=='.'){dfs(m,n);
// map[m+x][n+y]='.';}}}
}int main()
{while(scanf("%d%d",&w,&h)!=EOF){getchar();count=0;
// memset(vis,0,sizeof(vis));if(w==0&h==0) break;char temp;for(int i=0;i<h;i++){for(int j=0;j<w;j++){scanf("%c",&map[i][j]);if(map[i][j]=='@'){si=i; sj=j;}}scanf("%c",&temp);}map[si][sj]='#';//要防止那个人往回走 所以要把 走过的点设为'#'dfs(si,sj);printf("%d\n",count);}return 0;
}
BFS
ZOJ 1649 Rescue
题目大意就是一个人被困监狱中，他的朋友去救他，其中有点表示墙壁，警卫，走一格用一个时间单位，遇到警卫将其打死另外加一个时间单位，墙壁不能走过去，求所需的最少时间。
这题中求最小步骤的若干方案中的最小时间不一定是最优解一定要等到队列为空，BFS过程结束后才能求得最优解
代码如下：
#include <cstdio>
#include <cstring>
#include <queue>#define MAXMN 210
#define INF 1000000 //走到每个位置所需时间的初始值为无穷大using namespace std;struct point
{int x,y;int step;//走到当前位置所需的步数int time;//走到当前位置所需的时间
};queue<point> Q;
int N,M; //监狱的大小
char map[MAXMN][MAXMN];int mintime[MAXMN][MAXMN];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int ax,ay;//Angel所处的位置int BFS(point s)
{int i;Q.push(s);point hd;//从队列头出列的位置while(!Q.empty()){hd=Q.front();Q.pop();for(i=0;i<4;i++){//判断能否移动到相邻位置(x,y)int x=hd.x+dir[i][0],y=hd.y+dir[i][1];if(x>=0&&x<=N-1&&y>=0&&y<=M-1&&map[x][y]!='#')//排除边界和墙壁{point t;t.x=x;t.y=y;t.step=hd.step+1;t.time=hd.time+1;if(map[x][y]=='x') t.time++;//如果这种走法比之前走到(x,y)位置所花时间少 则把t入队列if(t.time<mintime[x][y]){mintime[x][y]=t.time;Q.push(t);}}}}return mintime[ax][ay];
}int main()
{while(scanf("%d%d",&N,&M)!=EOF){memset(map,0,sizeof(map));for(int i=0;i<N;i++)scanf("%s",map[i]);int sx,sy;point start;//朋友的位置for(int i=0;i<N;i++)for(int j=0;j<M;j++){mintime[i][j]=INF;if(map[i][j]=='a') {ax=i;ay=j;}else if(map[i][j]=='r') {sx=i;sy=j;}}start.x=sx; start.y=sy;start.step=0; start.time=0;mintime[sx][sy]=0;int mint=BFS(start);//返回到达Angel位置最少时间 有可能为INFif(mint<INF) printf("%d\n",mint);else printf("Poor ANGEL has to stay in the prison all his life.\n");}return 0;
}//待续 欢迎大家评论给点建议
这篇关于图论第二章图的遍历与活动网络问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
