首页 > 编程学习 > UVALive 7606 Percolation(DFS)

UVALive 7606 Percolation(DFS)

发布时间:2022/12/10 17:13:35

传送门:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5628


题意:有N*M的矩阵,0表示可以走,1表示不可以走,问是否有一条从第0行到第n-1行的通路

题解:枚举第0行每个可以走的点,然后搜索

#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
char mp[1005][1005];
bool vis[1005][1005];
int n,m,flag;
int to[][2]={0,1,0,-1,1,0,-1,0};
void dfs(int x,int y){if(flag)return;if(x==n-1) {flag=1;return;}for(int i=0;i<4;i++){int xx=x+to[i][0],yy=y+to[i][1];if(xx<0||yy<0||xx>=n||yy>=m||vis[xx][yy]||mp[xx][yy]=='1') continue;vis[xx][yy]=1;dfs(xx,yy);}
}
int main(){while(~scanf("%d%d",&n,&m)){for(int i=0;i<n;i++) scanf("%s",mp[i]);memset(vis,0,sizeof(vis));flag=0;for(int i=0;i<m;i++) {if(flag) break;if(!vis[0][i]&&mp[0][i]!='1') dfs(0,i);}printf("%s\n",flag?"YES":"NO");}return 0;
}



本文链接:https://www.ngui.cc/el/2314508.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000