仙岛求药

题目描述

少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。

叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。

迷阵由 M × N 个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。

现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。

现在要求你来帮助他实现这个目标。下图显示了一个迷阵的样例及李逍遥找到仙药的路线。

输入格式

输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始，两者均不大于 20。

M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含 N 个字符,不同字符分别代表不同含义:

1. @

   ：少年李逍遥所在的位置；

2. .

   ：可以安全通行的方格；

3. #

   ：有怪物的方格；

4. *

   ：仙药所在位置。

当在一行中读入的是两个零时，表示输入结束。

输出格式

对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。

如果他不可能找到仙药, 则输出 -1。

输入样例

8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
....@
9 6
.#..#.
.#.*.#
.####.
..#...
..#...
..#...
..#...
#.@.##
.#..#.
0 0
           

输出样例

10

8

-1

题解

BFS：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

struct node{
	int x, y;
}S;

const int N = 30;

int n, m;
char g[N][N];
int dist[N][N];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int bfs()
{
    memset(dist, -1, sizeof dist);
    queue<node> q;
    q.push(S);
    dist[S.x][S.y] = 0;
    
	while(q.size())
	{
		node t = q.front();
		q.pop();
		
		if(g[t.x][t.y] == '*') return dist[t.x][t.y];
		
		for (int i = 0; i < 4; i ++)
		{
			int a = t.x + dx[i], b = t.y + dy[i];
			if(a < 1 || a > n || b < 1 || b > m) continue;
			if(dist[a][b] != -1 || g[a][b] == '#') continue;
			
			q.push({a, b});
			dist[a][b] = dist[t.x][t.y] + 1;
		}
	}
	
	return -1;
}

int main()
{
	while(cin >> n >> m, n || m)
	{
		for (int i = 1; i <= n; i ++) cin >> g[i] + 1;
			
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= m; j ++)
				if(g[i][j] == '@') S = {i, j};
				
		cout << bfs() << endl;
	}
		
	return 0;	
}
           

ps：如果定义的是全局队列，每次输入前要把之前的队列清空。