由于新冠肺炎疫情的爆发，小明养在宿舍的小昆虫已经很久很久都没有人管了。小昆虫已经饿的不行了，必须出来找东西吃，可是出来之后需要走出一个迷宫。小昆虫每次可以朝上、下、左、右四个方向之一走一步，且只要走出任意一条边界线即可逃出迷宫。这只小昆虫曾感染过X星的一种奇异病毒，目前还没有发现任何副作用，但是却拥有了一项特异功能——破坏障碍物。假设小昆虫在一个NM的迷宫中，”@”代表小昆虫的初始位置，”.”代表可以通过的空地，””代表可以破坏的障碍物，”#”代表不可破坏的障碍物。请问小昆虫最少需要使用多少次特异功能才可以逃出迷宫?

区块链毕设网qklbishe.com为您提供问题的解答

由于新冠肺炎疫情的爆发，小明养在宿舍的小昆虫已经很久很久都没有人管了。小昆虫已经饿的不行了，必须出来找东西吃，可是出来之后需要走出一个迷宫。小昆虫每次可以朝上、下、左、右四个方向之一走一步，且只要走出任意一条边界线即可逃出迷宫。这只小昆虫曾感染过X星的一种奇异病毒，目前还没有发现任何副作用，但是却拥有了一项特异功能——破坏障碍物。假设小昆虫在一个N*M的迷宫中，”@”代表小昆虫的初始位置，”.”代表可以通过的空地，”*”代表可以破坏的障碍物，”#”代表不可破坏的障碍物。请问小昆虫最少需要使用多少次特异功能才可以逃出迷宫?

深搜加回溯就可以了，代码如下，niu’ke’bian’ji’ji

#include <bits/stdc++.h>

using namespace std;
int res = INT_MAX;
int m, n;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void back(vector<vector<char>>& tu, int x, int y, int count) {
if (x < 0 || y < 0 || x >= m || y >= n) {
res = min(res, count);
return;
}
if (tu[x][y] == ‘#’ || tu[x][y] == ‘A’)return;
if (tu[x][y] == ‘*’) {
count++;
}
char t = tu[x][y];
tu[x][y] = ‘A’;
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
back(tu, nx, ny, count);
}
tu[x][y] = t;
}
//用于测试
void print(vector<vector<char>> tu) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << tu[i][j] << ‘ ‘;
}
cout << endl;
}
}

int main() {
int K;
cin >> K;
int hang, lie;
while (K–) {
cin >> m >> n;
vector<vector<char>>tu(m, vector<char>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> tu[i][j];
if (tu[i][j] == ‘@’) {
hang = i;
lie = j;
}
}
}
back(tu, hang, lie, 0 );
if (res == INT_MAX)cout << -1 << endl;
else cout << res << endl;
res = INT_MAX;
}
return 0;
}

01:43

以上就是关于问题由于新冠肺炎疫情的爆发，小明养在宿舍的小昆虫已经很久很久都没有人管了。小昆虫已经饿的不行了，必须出来找东西吃，可是出来之后需要走出一个迷宫。小昆虫每次可以朝上、下、左、右四个方向之一走一步，且只要走出任意一条边界线即可逃出迷宫。这只小昆虫曾感染过X星的一种奇异病毒，目前还没有发现任何副作用，但是却拥有了一项特异功能——破坏障碍物。假设小昆虫在一个N*M的迷宫中，”@”代表小昆虫的初始位置，”.”代表可以通过的空地，”*”代表可以破坏的障碍物，”#”代表不可破坏的障碍物。请问小昆虫最少需要使用多少次特异功能才可以逃出迷宫?的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训