poj 1979 Red and Black 发表于 2016-08-12 | 分类于 DFS | | 阅读次数 DFS模板题 题目链接POJ 1979 题目大意给你一个矩阵,’@’表示起始点,’.’代表能走的路,’#’代表障碍,求最多能走的格子数。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<iostream>#include<cstdio>#include<algorithm>using namespace std;char a[25][25],vis[25][25];int m,n,sum=1;int jc(int x,int y )//判断是否出界{ return x>=1&&x<=m&&y>=1&&y<=n;}void dfs(int x,int y){ if(vis[x][y]) //判断是否遍历过 return; vis[x][y]=1; sum++; // 从四个方向遍历,也可使用方向数组 if(jc(x+1,y)&&a[x+1][y]==a[x][y]) dfs(x+1,y); if(jc(x,y+1)&&a[x][y+1]==a[x][y]) dfs(x,y+1); if(jc(x-1,y)&&a[x-1][y]==a[x][y]) dfs(x-1,y); if(jc(x,y-1)&&a[x][y-1]==a[x][y]) dfs(x,y-1);}int main(){ while(scanf("%d %d",&n,&m),m||n) { int i,j,d,f,k=0; for(i=1;i<=m;i++) { scanf("%s",a[i]+1); } memset(vis,0,sizeof(vis)); for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if(a[i][j]=='@') { a[i][j]='.'; d=i;f=j; } } } sum=0; dfs(d,f); k=sum; printf("%d\n",k); } return 0;} 坚持原创技术分享,您的支持将鼓励我继续创作! 赏 微信打赏 支付宝打赏