A46334. 密室逃脱小Y喜欢玩密室逃脱，每次游戏开始时，小Y会进入一个密室，她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明，解开线索对她来说并不难，但是她有一点懒，她希望在通关过程中移动次数最少。请你帮小Y计算她至少要移动多少次才能成功通关。密室是m行n列的格子矩阵，小Y从左上角(1,1)进入密室，密室中有三种格子:墙，以数字0标记路，以数字1标记隐藏线索处，以数字( > 1)标记, 代表该线…
填空题
困难
知识点
题目描述
密室逃脱
小Y喜欢玩密室逃脱，每次游戏开始时，小Y会进入一个密室，她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明，解开线索对她来说并不难，但是她有一点懒，她希望在通关过程中移动次数最少。请你帮小Y计算她至少要移动多少次才能成功通关。
密室是m行n列的格子矩阵，小Y从左上角(1,1)进入密室，密室中有三种格子:
墙，以数字0标记
路，以数字1标记
隐藏线索处，以数字( > 1)标记, 代表该线索的难度
小Y需要按照难度递增的顺序解开各个线索，逃脱密室。
输入
第一行是一个整数 T，表示输入包含 T 组数据，分别是不同的游戏中小Y所处的密室。 对于每组数据，第一行包括两个整数：m（1 <= m <= 100）、n（1 <= n <= 100）。 接下来 m 行，每行有n个数字，第 i 行的第 j 个数字表示密室中第 i 行第 j 列的格子的类型。 题目保证进入密室处(1,1)不是墙壁，线索的难度都不相同。
输出
对于每组数据，你需要输出一个整数，表示小Y在这个密室中至少要移动多少次才能成功通关。 如果小Y不可能解开所有线索，输出-1.
样例输入
2
3 3
1 3 2
1 0 4
10 6 5
3 3
1 3 2
0 0 0
10 6 5
样例输出
8
-1
提示
样例解释：由于需要按难度顺序解开线索，在第一组数据中，小Y第一次移动到3时不能解密，在完成2之后需要回到3.最后小Y解开10时，她成功通关。
参考答案
//示例代码 条件+广搜
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int m,n;
int maze[104][104] = {};
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
bool legal(int x, int y){
if(0 <= x && x< m && 0 <= y && y < n && maze[x][y] != 0)return 1;
return 0;
}
struct Node{
int x, y, k, t;
};
int main()
{
int T;
cin >> T;
while(T--){
memset(maze, 0, sizeof(maze));
int vis[104][104] = {};
memset(vis, 0xff, sizeof(vis));
int S[10050] = {};
int cnt = 0;
cin >> m >> n;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin >> maze[i][j];
if (maze[i][j] > 1) {
S[cnt++] = maze[i][j];
}
}
}
queue<Node> open;
sort(S, S + cnt);
if (maze[0][0] == S[0]) {
open.push({0, 0, 1, 0});
vis[0][0] = 1;
}
else {
open.push({0, 0, 0, 0});
vis[0][0] = 0;
}
bool flag = 0;
while (!open.empty()) {
Node temp = open.front();
open.pop();
if (temp.k == cnt) {
flag = 1;
cout << temp.t << endl;
break;
}
for (int i = 0; i < 4; i++) {
int x = temp.x + dx[i], y = temp.y + dy[i], k = temp.k;
if (!legal(x,y)) continue;
if (maze[x][y] == S[k]) k++;
if (vis[x][y] >= k) continue;
vis[x][y] = k;
open.push({x, y, k, temp.t + 1});
}
}
if (!flag) cout << -1 << endl;
}
return 0;
}
上一题
下一题