问题描述
少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。
输入
输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义: 1) ‘@’：少年李逍遥所在的位置； 2) ‘.’：可以安全通行的方格； 3) ‘#’：有怪物的方格； 4) ‘*’：仙药所在位置。 当在一行中读入的是两个零时，表示输入结束。
输出
对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。
样例
INPUT
8 8
.@##...# #....#.# #.#.##.. ..#.###. #.#...#. ..###.#.
OUTPUT
10
解题思路
BFS。
求最短路径且有地图，优先使用BFS。为了每次用队列能完整地存储每个点的信息（坐标x，y和步数sum），创建一个结构体
struct road{
int x;//横坐标
int y;//纵坐标
int sum;//已走的步数
};
为清楚地描述行进的方向，创建一个二维数组
int dir[4][2] = {
{1, 0},{-1, 0},{0, 1},{0, -1}
};//向右、向左、向上、向下（在后面遍历的时候加上相应的数字）
创建队列后，先放入初始信息即起点的x，y，sum=0；之后不断进行四个方位的扫描，如果满足行进条件（本题中是不越界且！=‘#’），则对此处进行标记（标记过的地方就不必再走了）。
如果找到了仙药，则返回sum+1；如果没找到，则让刚刚查询的这个点入队，sum++，循环往复。
完整代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <iomanip>
#include <queue>
using namespace std;
int flag[21][21];
char s[21][21];
int n, m;
int MapBeginX, MapBeginY, MapEndX, MapEndY;//用于保存起点和终点位置
struct road{
int x;
int y;
int sum;
};
queue<road> Q;
int dir[4][2] = {
{1, 0},{-1, 0},{0, 1},{0, -1}
};
int bfs(int be, int en){//参数为起点和终点
flag[be][en] = 1;//标记起点
road rr;
rr.x = be;
rr.y = en;
rr.sum = 0;
Q.push(rr);//存储起点信息
while(!Q.empty()){
road r = Q.front();
Q.pop();
for(int i = 0; i < 4; i++){//开始四处遍历
int temx = r.x + dir[i][0];
int temy = r.y + dir[i][1];
if(temx >= 0&&temx <n&&temy >= 0&&temy <m&&(!flag[temx][temy])&&(s[temx][temy] == '.')){//满足条件
flag[temx][temy] = 1;//标记
if(temx == MapEndX&&temy == MapEndY){//找到
return r.sum + 1;
}
//未找到
road rrr;
rrr.x = temx;
rrr.y = temy;
rrr.sum = r.sum + 1;
Q.push(rrr);
}
}
}
return 0;
}
int main(){
cin>>n>>m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin>>s[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(s[i][j] == '@'){//保存起点终点坐标
MapBeginX = i;
MapBeginY = j;
}else if(s[i][j] == '*'){
MapEndX = i;
MapEndY = j;
s[i][j] = '.';//保存过后置'.'保证搜索到终点时满足条件
}
}
}
int X = bfs(MapBeginX, MapBeginY);
if(X) cout<<X<<endl;
else cout<<"-1"<<endl;//达不到时返回-1
return 0;
}
