杭州网站优化方案,怎么做资源类网站,产品网页设计公司,seo科技网1112. 迷宫 - AcWing题库
一天Extense在森林里探险的时候不小心走入了一个迷宫#xff0c;迷宫可以看成是由 n∗n 的格点组成#xff0c;每个格点只有2种状态#xff0c;.和##xff0c;前者表示可以通行后者表示不能通行。
同时当Extense处在某个格点时#xff0c;他只…1112. 迷宫 - AcWing题库
一天Extense在森林里探险的时候不小心走入了一个迷宫迷宫可以看成是由 n∗n 的格点组成每个格点只有2种状态.和#前者表示可以通行后者表示不能通行。
同时当Extense处在某个格点时他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上Extense想要从点A走到点B问在不走出迷宫的情况下能不能办到。
如果起点或者终点有一个不能通行(为#)则看成无法办到。
注意A、B不一定是两个不同的点。
输入格式
第1行是测试数据的组数 k后面跟着 k 组输入。
每组测试数据的第1行是一个正整数 n表示迷宫的规模是 n∗n 的。
接下来是一个 n∗n 的矩阵矩阵中的元素为.或者#。
再接下来一行是 4 个整数 ha,la,hb,lb描述 A 处在第 ha 行, 第 la 列B 处在第 hb 行, 第 lb 列。
注意到 ha,la,hb,lb 全部是从 0 开始计数的。
输出格式
k行每行输出对应一个输入。
能办到则输出“YES”否则输出“NO”。
数据范围
1≤n≤100
输入样例
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0输出样例:
YES
NO
解析
使用dfs进行判断代码要比bfs简洁
dfs代码
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
using namespace std;
typedef long long LL;
const int N 1e2 2;
int n, ha, la, hb, lb;
char str[N][N];
bool vis[N][N];
int dx[4] { -1,0,1,0 }, dy[4] { 0,1,0,-1 };
bool dfs(int x, int y) {if (str[x][y] #)return false;if (x hb y lb)return true;for (int i 0; i 4; i) {int a x dx[i], b y dy[i];if (a 0 || a n || b 0 || b n)continue;if (vis[a][b])continue;vis[a][b] 1;if (dfs(a, b))return true;}return false;
}int main() {int T;cin T;while (T--) {cin n;for (int i 0; i n; i) {scanf(%s, str[i]);}cin ha la hb lb;memset(vis, 0, sizeof vis);if (dfs(ha, la))cout YES endl;else cout NO endl;}return 0;
}BFS代码
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
using namespace std;
typedef long long LL;
const int N 1e2 2;
int n,ha,la,hb,lb;
char str[N][N];
typedef pairint, int PII;
bool vis[N][N];string bfs() {string ret1 YES, ret2 NO;if (str[ha][la] # || str[hb][lb] #)return ret2;int dx[4] { -1,0,1,0 }, dy[4] { 0,1,0,-1 };memset(vis, 0, sizeof vis);queuePIIq;q.push({ ha,la });vis[ha][la] 1;while (!q.empty()) {auto t q.front();q.pop();if (t.first hb t.second lb)return ret1;for (int i 0; i 4; i) {int a t.first dx[i], b t.second dy[i];if (a 0 || a n || b 0 || b n)continue;if (str[a][b] #||vis[a][b])continue;vis[a][b] 1;q.push({ a,b });}}return ret2;
}int main() {int T;cin T;while (T--) {cin n;for (int i 0; i n; i) {scanf(%s, str[i]);}cin ha la hb lb;cout bfs() endl;}return 0;
}
