nyoj1246 逃离妖洞 BFS

2019-11-10 18:11:06

字体：大中小

来源：转载

供稿：网友

逃离妖洞

描述

唐僧不小心又掉入妖怪的迷宫了。这个迷宫有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 11 32 23 3 1....#....1 13 32 3 1..#.#.1 12 3样例输出33-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;}如有不当之处欢迎指出！