信息学奥赛一本通 1215：迷宫 搜索与回溯算法
同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。每组测试数据的第1行是一个正整数n(1≤n≤100)，表示迷宫的规模是n×n的。接下来是一个n×n的矩阵，矩阵中的元素为。再接下来一行是4个整数ha,la,hb,lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。一天
1215：迷宫
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n×n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。
【输入】
第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n(1≤n≤100)，表示迷宫的规模是n×n的。接下来是一个n×n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha,la,hb,lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha,la,hb,lb全部是从0开始计数的。
【输出】
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。
【输入样例】
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
【输出样例】
YES
NO
解析：搜索回溯，详见代码：
#include<bits/stdc++.h>
using namespace std;
int k, n;
char a[105][105];//地图
bool b[105][105];//标记是否走过
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool flag;
int ha, la, hb, lb;
void dfs(int x, int y) {
//cout<<x<<":"<<y<<endl;
if (x == hb && y == lb) { //如果找到出口，标记成功
flag = 1;
return;
}
if (flag == 1) return; //如果已经找到出口，返回
for (int i = 0; i < 4; i++) { //四个方向搜索
int xx = x + dx[i];
int yy = y + dy[i];
//满足没有出界，并且没有走过，并且可以走（不是#）
if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && b[xx][yy] == 0 && a[xx][yy] != '#') {
b[xx][yy] = 1; //标记
dfs(xx, yy); //继续搜索
//b[xx][yy]=0;//清除标记
}
}
}
int main() {
cin >> k;
while (k--) {
cin >> n;
flag = 0;
for (int i = 1; i <= n; i++) { //输入
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
cin >> ha >> la >> hb >> lb;
ha++;
hb++;
la++;
lb++;
if (a[ha][la] == '#' || a[hb][lb] == '#') { //判断出入口是否合法
cout << "NO" << endl;
continue;
}
for (int i = 1; i <= n; i++) { //清空标记
for (int j = 1; j <= n; j++) {
b[i][j] = 0;
}
}
b[ha][la] = 1; //标记起点
dfs(ha, la); //从起点开始搜索
if (flag == 1) { //判断结果
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
10
0- 0
已为社区贡献20条内容
所有评论(0)