欢迎访问==> 【考研OR保研】机试题
题目描述
给定一个 $m × n$ ($m$ 行, $n$ 列)的迷宫,迷宫中有两个位置,gloria 想从迷宫的一个位置走到另外一个位置,当然迷宫中有些地方是空地,gloria 可以穿越,有些地方是障碍,她必须绕行,从迷宫的一个位置,只能走到与它相邻的 $4$ 个位置中,当然在行走过程中,gloria 不能走到迷宫外面去。
令人头痛的是,gloria 是个没什么方向感的人,因此,她在行走过程中,不能转太多弯了,否则她会晕倒的。
我们假定给定的两个位置都是空地,初始时,gloria 所面向的方向未定,她可以选择 $4$ 个方向的任何一个出发,而不算成一次转弯。
gloria 能从一个位置走到另外一个位置吗?
输入格式
第 $1$ 行为一个整数 $T$,表示测试数据的个数,接下来为 $T$ 组测试数据,每组测试数据中,
第 $1$ 行为两个整数 $m, n$,分别表示迷宫的行数和列数,接下来 $m$ 行,每行包括 $n$ 个字符,其中字符 .
表示该位置为空地,字符 *
表示该位置为障碍,输入数据中只有这两种字符,每组测试数据的最后一行为 $5$ 个整数 $k, x_1, y_1, x_2, y_2$,其中 $k$ 表示 gloria 最多能转的弯数,$(x_1, y_1), (x_2, y_2)$ 表示两个位置,其中 $x_1,x_2$ 对应列,$y_1,y_2$ 对应行。
输出格式
每组测试数据对应为一行,若 gloria 能从一个位置走到另外一个位置,输出 yes
,否则输出 no
。
数据范围
$1 \\le T \\le 100$,
$1 \\le m,n \\le 100$,
$1 \\le k \\le 10$,
$1 \\le x_1,x_2 \\le n$,
$1 \\le y_1,y_2 \\le m$,
保证给定的两个位置不同,且一定是空地。
输入样例:
2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3
输出样例:
no
yes
C++ 代码
/*
本题思路应该很简单,BFS或者DFS都行,但是需要优化
优化:用一个mx[][]数组记录走到当前点最少的拐弯次数
如果当前走到这个点时候转弯次数多于最少的转弯次数,则直接进行剪枝
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
int T, n, m, mx[N][N];
char g[N][N];
int k, sx, sy, gx, gy;
bool flag;
void dfs(int x, int y, int u, int dir)
{
//核心剪枝优化!!!
if(u > mx[x][y]) return;
mx[x][y] = u;
if(u > k) return;
if(x == gx && y == gy)
{
flag = true;
return;
}
g[x][y] = '#';
for(int t = 0; t < 4; t ++)
{
int nx = x + dx[t], ny = y + dy[t];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == '.')
{
if(dir == t) dfs(nx, ny, u, t);
else dfs(nx, ny, u + 1, t);
}
}
g[x][y] = '.';
}
int main()
{
cin >> T;
while(T -- )
{
flag = false;
memset(mx, 0x3f, sizeof mx);
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> g[i] + 1;
cin >> k >> sy >> sx >> gy >> gx;
dfs(sx, sy, -1, -1);
if(flag) puts("yes");
else puts("no");
}
return 0;
}
666