NOI OpenJudge 题库 6264 走出迷宫

Algorithms
NOI OpenJudge, 宽度优先搜索

描述

当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。
假设你已经得到了一个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;
}
分享到