codevs1215 迷宫

2019-11-09 21:17:23

字体：大中小

来源：转载

供稿：网友

用dfs做的，还不嫌累的用if，当然bfs也很好做（代码很丑）。

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;int n;bool flag;bool vis[50][50];char s[50][50];void dfs(int x,int y){ if(x == n&&y == n) { flag = 1; return ; } vis[x][y] = 1; if(s[x+1][y] == '.'&&!vis[x+1][y]) { vis[x+1][y]=1; dfs(x+1,y); } if(s[x-1][y] == '.'&&!vis[x-1][y]) { vis[x-1][y]=1; dfs(x-1,y); } if(s[x][y+1] == '.'&&!vis[x][y+1]) { vis[x][y+1]=1; dfs(x,y+1); } if(s[x][y-1] == '.'&&!vis[x][y-1]) { vis[x][y-1]=1; dfs(x,y-1); }}int main(){ int t; cin>>t; for(int k = 1; k <= t; k ++) { flag = 0; memset(vis,0,sizeof(vis)); cin>>n; for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) { cin>>s[i][j]; } for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) { if(s[i][j] == 's'||s[i][j] == 'e') { s[i][j] ='.'; } } dfs(1,1); if(flag) puts("YES"); else puts("NO"); } return 0;}

上一篇：Polya问题

下一篇：高斯消元模板