NOI OpenJudge 题库 6264 走出迷宫

描述

当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。

输入

第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。
接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符’.’表示空地,’#’表示墙,’S’表示起点,’T’表示出口。

输出

输出从起点到出口最少需要走的步数。

样例输入

1
2
3
4
3 3
S#T
.#.
...

样例输出

1
6

分析

最近在刷 OpenJudge ,怎么说也得拿个 200 分换省三呢。

宽搜入门题,试了一把 STL 队列,写完觉得链表、栈、队列这种东西还是自己实现算了 …… 这些用 STL 写实在太花哨,也并没有方便太多,但是 STL 的优先队列、堆倒还是很有用的。

代码

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
#define loop(i,n) for(int i=0;i<n;i++)
const int INF=2147483647;
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
char maze[110][110];
int dis[110][110];
bool map[110][110];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
typedef pair<int,int> matrix;
matrix start,end;
queue<matrix> q;
int n,m;
void init()
{
memset(map,0,sizeof(map));
loop(i,110)
loop(j,110)
dis[i][j]=INF;
cin >>n>>m;
loop(i,n)
loop(j,m)
{
cin >>maze[i][j];
if(maze[i][j]=='S')
{
start.first=i;
start.second=j;
map[i][j]=0;
}
if(maze[i][j]=='T')
{
end.first=i;
end.second=j;
map[i][j]=0;
}
if(maze[i][j]=='.')
map[i][j]=0;
if(maze[i][j]=='#')
map[i][j]=1;
}
}
int check(int x,int y)
{
if(dis[x][y]==INF && !map[x][y] && x>=0 && x<n && y>=0 && y<m)
return 1;
return 0;
}
int bfs()
{
dis[start.first][start.second]=0;
q.push(matrix(start.first,start.second));
while(q.size())
{
matrix tmp=q.front();
q.pop();
if(tmp.first==end.first && tmp.second==end.second)
break;
loop(i,4)
{
int curx=tmp.first+dx[i],cury=tmp.second+dy[i];
if(check(curx,cury))
{
q.push(matrix(curx,cury));
dis[curx][cury]=dis[tmp.first][tmp.second]+1;
}
}
}
return dis[end.first][end.second];
}
int main()
{
init();
cout <<bfs()<<endl;
return 0;
}
分享到 评论