A40804. 迷宫与陷阱
填空题
困难
知识点
题目描述
迷宫与陷阱
题目描述
小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 N x N 个格子组成的2D迷宫。
小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫，每一步，他可以移动到上下左右相邻的格子中。
迷宫中有些格子小明可以经过，我们用 '.' 表示；有些格子是墙壁，小明不能经过，我们用 '#' 表示。
此外，有些格子上有陷阱，我们用 'X' 表示，除非小明处于无敌状态，否则不能经过；有些格子上有无敌道具，我们用 '%' 表示。
当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 K 步，之后如果再次到达该格子不会获得无敌状态了。
处于无敌状态时，可以经过有陷阱的格子，但是不会拆除/毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。
给定迷宫，请你计算小明最少经过几步可以离开迷宫？
输入格式
第一行包含两个整数 N 和 K。
以下 N 行包含一个 N x N 的矩阵（矩阵保证左上角和右下角是 ‘.’）。
输出格式
一个整数表示答案。
如果小明不能离开迷宫，输出 -1。
样例输入1
5 3
...XX
##%#.
...#.
.###.
.....
1
2
3
4
5
6
样例输出1
10
样例输入2
5 1
...XX
##%#.
...#.
.###.
.....
1
2
3
4
5
6
样例输出2
12
数据范围
1 ≤ N ≤ 1000
1 ≤ K ≤ 10
参考答案
const int N = 1e3 + 10;
int n, k;
char mp[N][N];
bool vis[N][N][11];
int ans;
int ax[4] = {0, 1, 0, -1};
int ay[4] = {1, 0, -1, 0};
struct node {
//结构体定义状态， x, y 为状态， k为当前剩余的无敌时间，
//s为到达这个状态的步数
int x, y, k, s;
node (int cx, int cy, int ck, int cs) {
x = cx, y = cy, k = ck, s = cs;
}
};
int bfs() {
queue<node> que;
//初始化(0, 0)点
vis[0][0][0] = true;
que.push(node(0, 0, 0, 0));
while (!que.empty()) {
//取出队头元素
node u = que.front();
que.pop();
//到达终点，返回答案
if (u.x == n - 1 && u.y == n - 1) {
return u.s;
}
//遍历上下左右四个点
for (int i = 0; i < 4; i++) {
int tx = u.x + ax[i];
int ty = u.y + ay[i];
//越界或者为墙壁，不可达
if (tx < 0 || ty < 0 || tx >= n || ty >= n || mp[tx][ty] == '#') {
continue;
}
//(tx, ty)处有一个无敌道具， 且此状态未访问过
if (mp[tx][ty] == '%' && !vis[tx][ty][k]) {
vis[tx][ty][k] = true;
que.push(node(tx, ty, k, u.s + 1));
} else {
//当前无敌，无论前方是陷阱还是道路都可走
if (u.k && !vis[tx][ty][u.k - 1]) {
vis[tx][ty][u.k - 1] = true;
que.push(node(tx, ty, u.k - 1, u.s + 1));
//当前不无敌， 而且前方为道路
} else if (mp[tx][ty] == '.' && !u.k && !vis[tx][ty][0]) {
vis[tx][ty][0] = true;
que.push(node(tx, ty, 0, u.s + 1));
}
}
}
}
//可到达的遍历完了但是仍然没有到达终点，表示不可达，返回-1
return -1;
}
int main() {
scanf("%d%d", &n, &k); //读入图的大小和无敌时间
for (int i = 0; i < n; i++) { //输入图
scanf("%s", mp[i]);
}
ans = bfs(); //调用BFS函数求解，无解时返回-1
cout << ans;
return 0;
}
上一题
下一题