逃離妖洞

唐僧不小心又掉入妖怪的迷宮了。這個迷宮有n行m列，共n*m個方格。有的方格是空的，唐僧可以站在上面，有些是有障礙物的不能站。每次唐僧可以移動到相鄰的8個空方格上。但是有些情況不能移動，即從兩個方格的縫隙中移動，如圖：

為了逃出妖怪的洞穴，唐僧需要觸發悟空在某個方格留下的寶物，寶物都是留在空的方格中的。如果唐僧站在某個留有寶物的方格中，那么這個寶物就會被觸發。為了逃離妖洞，唐僧務必按順序依次觸發K個寶物，當最后一個寶物被觸發后，唐僧將會逃離妖洞。

現在唐僧已經知道這個迷宮中的障礙方格和有寶物的方格情況，開始唐僧站在一個給定的方格。問他是否可以逃離妖洞？

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;}如有不當之處歡迎指出！