逃离妖洞
- 描述
-
唐僧不小心又掉入妖怪的迷宫了。这个迷宫有n行m列，共n*m个方格。有的方格是空的，唐僧可以站在上面，有些是有障碍物的不能站。每次唐僧可以移动到相邻的8个空方格上。但是有些情况不能移动，即从两个方格的缝隙中移动，如图：
为了逃出妖怪的洞穴，唐僧需要触发悟空在某个方格留下的宝物，宝物都是留在空的方格中的。如果唐僧站在某个留有宝物的方格中，那么这个宝物就会被触发。为了逃离妖洞，唐僧务必按顺序依次触发K个宝物，当最后一个宝物被触发后，唐僧将会逃离妖洞。
现在唐僧已经知道这个迷宫中的障碍方格和有宝物的方格情况，开始唐僧站在一个给定的方格。问他是否可以逃离妖洞？
- 输入
- 一共有T（T<=20）组测试数据。
每组含有行数n，列数m。（2<=n,m<=100）以及放有宝物的K（1<= K <=10）个方格。
下面n行，每行包含m个字符，用'.'表示空的方格，用'#'表示有障碍物的方格。
下面一行是起点位置（x，y），保证是空的方格。
下面的K行表示藏有宝物的空方格的位置，藏有宝物的方格是空的，没有障碍物。两个宝物不会放在同一个空方格中。需要按所给宝物顺序依次触发宝物。 - 输出
- 输出为了逃离妖洞，最少需要多少次移动。如果不能逃离，输出-1。
- 样例输入
-
3 3 3 2 ... ... ... 1 1 1 3 2 2 3 3 1 ... .#. ... 1 1 3 3 2 3 1 ..# .#. 1 1 2 3
- 样例输出
-
3 3 -1
值得注意的地方
1. 宝物必须依次触发，也就是说不能提前通过未触发的宝物。
2. 起点可能位于某个宝物上面，如果不是位于第1个宝物的坐标，那么唐僧不可能逃离的。
AC代码：
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 100 + 5;
int d[maxn][maxn];
char G[maxn][maxn];
int n, m, k;
const int dx[] = {1,-1,0,0, 1,-1,-1,1};
const int dy[] = {0,0,1,-1, -1,-1,1,1};
struct node{
int x, y;
node(){
}
node(int x, int y):x(x), y(y){
}
}h[15];
int bfs(int x, int y, char g){
memset(d, -1, sizeof(d));
queue<node>q;
q.push(node(x, y));
d[x][y] = 0;
while(!q.empty()){
node p = q.front();
q.pop();
x = p.x, y = p.y;
if(G[x][y] == g) return d[x][y];
for(int i = 0; i < 8; ++i){
int px = x + dx[i], py = y + dy[i];
if(px < 0 || px >= n || py < 0 || py >= m || G[px][py] == '#' || G[px][py] > g || d[px][py] != -1) continue;
if(i >= 4 && G[x + dx[i]][y] == '#' && G[x][y + dy[i]] == '#') continue;
q.push(node(px, py));
d[px][py] = d[x][y] + 1;
}
}
return -1;
}
int solve(int x, int y){
if(G[x][y] == '#') return -1;
if(G[x][y] != '.' && G[x][y] > '0') return -1;
int ans = 0;
for(int i = 0; i < k; ++i){
int step = bfs(x, y, '0' + i);
if(step == -1) return -1;
ans += step;
x = h[i].x, y = h[i].y;
}
return ans;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d%d", &n, &m, &k);
for(int i = 0; i < n; ++i){
scanf("%s", G[i]);
}
int x, y;
scanf("%d%d", &x, &y);
int x1, y1; //宝物的坐标
for(int i = 0; i < k; ++i){
scanf("%d%d", &x1, &y1);
h[i] = node(x1 - 1, y1 - 1);
G[x1 - 1][y1 - 1] = i + '0';
}
printf("%d\n",solve(x - 1, y - 1));
}
return 0;
}
如有不当之处欢迎指出！