仙岛求药

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
总时间限制: 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

upload successful

使用栈进行dfs，统计步数，取最小。
也可bfs，bfs搜到目标即可停止搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
const int INF = (1<<31)-1;
using namespace std;

typedef struct
{
	int x,y,depth;
}Point;
char maze[50][50];
int vis[50][50];
stack<Point> s;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int main()
{
	int M,N;
	int minstep, stepcnt;
	Point L, Tar;
	while(cin>>M>>N)
	{
		minstep = INF;
		stepcnt = 0;
		if(!M&&!N)
			break;
		getchar();
		for(int i=0;i<M;++i)
		{
			for(int j=0;j<N;++j)
			{
				scanf("%c", &maze[i][j]);
				vis[i][j] = 0;
				if(maze[i][j]=='@')
					L.x=i, L.y=j, L.depth=0;
				else if(maze[i][j] == '*')
					Tar.x = i, Tar.y = j;
			}
			getchar();
		}
		/*
		for(int i=0;i<M;++i)
		{
			for(int j=0;j<N;++j)
			{
				printf("%c", maze[i][j]);
			}
			putchar('\n');
		}
		*/
		s.push(L);
		while(!s.empty())
		{
			Point t = s.top();
			//cout<<t.x<<','<<t.y<<','<<t.depth<<endl;
			if(t.x==Tar.x&&t.y==Tar.y)
			{
				minstep = minstep<t.depth? minstep:t.depth;
				s.pop();
				continue;
			}
			vis[t.x][t.y] = 1;
			s.pop();
			for(int i=0;i<4;++i)
			{
				Point tmp;
				tmp.x = t.x+dx[i];
				tmp.y = t.y+dy[i];
				tmp.depth = t.depth+1;
				if(maze[tmp.x][tmp.y]!='#'&&!vis[tmp.x][tmp.y]&&tmp.x>=0&&tmp.x<M&&tmp.y>=0&&tmp.y<N)
				{
					//cout<<'>'<<tmp.x<<','<<tmp.y<<endl;
					s.push(tmp);
				}

			}
		}
		cout<<(minstep==INF?-1:minstep)<<endl;
	}

	return 0;
}