国内网站建设,html模板引擎,免费制作广告图,迈创网站建设无穷迷宫
jzoj 3924
题目大意
有一个n*m的迷宫#xff0c;有墙#xff08;##xff09;#xff0c;路#xff08;.#xff09;#xff0c;和你的位置#xff08;S#xff09;#xff0c;这个迷宫会复制无数份拼在一起#xff0c;问你能不能不停地走下去
输入样例…无穷迷宫
jzoj 3924
题目大意
有一个n*m的迷宫有墙#路.和你的位置S这个迷宫会复制无数份拼在一起问你能不能不停地走下去
输入样例
2
5 4
##.#
##S#
#..#
#.##
#..#
5 4
##.#
##S#
#..#
..#.
#.##输出样例
Yes
No 样例解释
第一组测试数据中机器人不断沿着路径向上走即可。 第二组测试数据中机器人无论向哪个方向走都会是死路。
数据范围
50% 的数据1⩽N,M⩽50.1 \leqslant N, M \leqslant 50.1⩽N,M⩽50. 100% 的数据1⩽N,M⩽15001⩽T⩽4.1 \leqslant N, M \leqslant 15001 \leqslant T \leqslant 4.1⩽N,M⩽15001⩽T⩽4.
解题思路
因为我们不能尝试不停的走下去那我们想一下 如果我们能做到不同迷宫的同一位置那我们就可以用同样的方式再走到另一个迷宫的同一位置那就是可以无限得走下去 那我们dfs时保存在迷宫内的位置也要保存对于第一个迷宫的位置这样就可以判断是不是不同迷宫的统一个位置
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
int t, n, m, x, y, ans, f[2000][2000][5];
char a[2000][2000];
const int dx[4] {1, 0, -1, 0};
const int dy[4] {0, 1, 0, -1};
int sx(int x)
{return (x n - 1) % n 1;
}
int sy(int y)
{return (y m - 1) % m 1;
}
void dfs(int x, int y, int lx, int ly)//xy是%了的lxly是没%的
{if (f[x][y][0] (f[x][y][1] ! lx || f[x][y][2] ! ly))//之前是否在别的迷宫到过这个位置{ans 1;return;}f[x][y][0] 1;f[x][y][1] lx;f[x][y][2] ly;for (int i 0; i 4 !ans; i)if (a[sx(x dx[i])][sy(y dy[i])] ! # (!f[sx(x dx[i])][sy(y dy[i])][0] || f[sx(x dx[i])][sy(y dy[i])][1] ! lx dx[i] || f[sx(x dx[i])][sy(y dy[i])][2] ! ly dy[i]))//不是同一个迷宫或没到过且不是墙dfs(sx(x dx[i]), sy(y dy[i]), lx dx[i], ly dy[i]);
}
int main()
{scanf(%d, t);while(t--){memset(f, 0, sizeof(f));ans 0;scanf(%d %d, n, m);for (int i 1; i n; i)for (int j 1; j m; j){cina[i][j];if (a[i][j] S)x i, y j;}dfs(x, y, x, y);if (ans) printf(Yes\n);else printf(No\n);}return 0;
}
