不同 ring ++ 数据 printf while har pre
总时间限制: 1000ms
内存限制: 65536kB 描述
少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由 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
- 1#include 2#include 3#include 4#include 5#include 6#define M 21 7 8 using namespace std;
- 9 10 int m,
- n,
- sx,
- sy,
- ex,
- ey;
- 11 int jz[M][M];
- 12 bool v[M][M];
- 13 int dx[4] = {
- 0,
- 0,
- 1,
- -1
- },
- 14 dy[4] = {
- 1,
- -1,
- 0,
- 0
- }; //几个方向
- 15 16 struct a {
- 17 int x,
- y,
- step;
- 18
- }
- nex,
- noww;
- 19 20 queueq;
- 21 22 void bfs() 23 {
- 24
- if (sx == ex && sy == ey) //防止出现起点等于终点的情况
- 25 {
- 26 printf("0\n");
- 27
- return;
- 28
- }
- 29
- while (!q.empty()) q.pop(); //因为有多组数据需要进行清空
- 30 noww.x = sx;
- noww.y = sy;
- noww.step = 0; //初始化
- 31 v[sx][sy] = 1; //进行标记已经被访问
- 32 q.push(noww);
- 33
- while (!q.empty()) 34 {
- 35 noww = q.front(); //取出队头元素
- 36 q.pop();
- 37
- for (int i = 0; i < 4; i++) 38 {
- 39 int xx = noww.x + dx[i],
- yy = noww.y + dy[i];
- 40
- if (xx > 0 && xx <= m && yy > 0 && yy <= n && !v[xx][yy] && jz[xx][yy]) 41 {
- 42
- if (xx == ex && yy == ey) //如果到达终点
- 43 {
- 44 printf("%d\n", noww.step + 1); //输出答案
- 45
- return; //不能够写break!因为break只能够跳出for循环
- 46
- }
- 47 nex.x = xx;
- nex.y = yy;
- nex.step = noww.step + 1;
- 48 v[xx][yy] = 1; //标记
- 49 q.push(nex); //进队
- 50
- }
- 51
- }
- 52
- }
- 53 cout << "-1" < //没有找到输出-1
- 54
- }
- 55 56 int main() 57 {
- 58 char ch;
- 59
- while (scanf("%d%d", &m, &n) != EOF) //在不清楚拥有几组数据的情况下
- 60 {
- 61
- if (m != 0 && n != 0) 62 {
- 63 memset(jz, 0, sizeof(jz));
- 64 memset(v, 0, sizeof(v));
- 65
- for (int i = 1; i <= m; i++) 66
- for (int j = 1; j <= n; j++) 67 {
- 68 cin >> ch;
- 69
- if (ch == '@') //李(起)逍(点)遥
- 70 {
- 71 sx = i;
- sy = j;
- 72
- }
- 73
- if (ch == ' * ') //仙(终)药(点)
- 74 {
- 75 ex = i;
- ey = j;
- 76
- }
- 77
- if (ch == '#') //怪(障)物(碍)
- 78 {
- 79
- continue;
- 80
- }
- 81 jz[i][j] = 1;
- 82
- }
- 83 bfs();
- 84
- }
- 85
- else break;
- 86
- }
- 87
- return 0;
- 88
- }
NOI 2727: 仙岛求药 x
来源: http://www.bubuko.com/infodetail-2038836.html