UVA10047-扩展BFS

Veröffentlicht am   |  

这道题一开始没有什么思路，后来上网看了下别人的题解才发现原来就是一种BFS。

之前迷宫类题目（无加权），直接可以用BFS来做，但是这道题加入了另外两个条件——方向和颜色。其实这就相当于将原来的二维空间扩展到了四维空间。我们要做的就是在这四维状态空间中进行搜索。和原来的二维情况不同的是，这个题目加入了转向的要素，也就是说相邻状态的距离间隔不一定是1，这就比较坑爹，不能直接使用队列来进行存储，需要用一个优先队列（小顶堆）。也许有更好的方案，请务必告诉我。

有一个需要注意的点是，每一次转向所处的状态不能漏掉（转向后还没开始行走），我一开始就是没有注意这一点被坑了。

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
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
char maze[25][25];
bool vis[25][25][5][4];
struct  Node{
    int r;
    int c;
    int color;
    int d;
    int time;
};
int main()
{
    int m, n;
    auto cmp = [](Node left, Node right) { return (left.time) > (right.time);};
    priority_queue<Node, vector<Node>, decltype(cmp)> Q(cmp);
    int kase = 1;
    while (cin >> m >> n)
    {
        if (m == 0)
            break;
        while (!Q.empty())
            Q.pop();
        memset(vis, 0, sizeof(vis));
        for (int i = 0;i < m;i++)
            for (int j = 0;j < n;j++)
                cin >> maze[i][j];
        Node start;
        for (int i = 0;i < m;i++)
            for (int j = 0;j < n;j++)
            {
                if (maze[i][j] == 'S')
                {
                    start.r = i;
                    start.c = j;
                    start.color = 0;
                    start.time = 0;
                    start.d = 0;
                }
            }
        Q.push(start);
        int ans = 0;
        //bfs
        int step[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        while(!Q.empty())
        {
            Node cur = Q.top();
            Q.pop();
            vis[cur.r][cur.c][cur.color][cur.d] = true;
            for (int i = 0;i < 4;i++)
            {
                int nr, nc, ncolor, nd, ntime;
                if (cur.d == i)
                {
                    ntime = cur.time + 1;
                    nd = i;
                    nr = cur.r + step[i][0];
                    nc = cur.c + step[i][1];
                    ncolor = (cur.color + 1)%5;
                } else
                {
                    if (abs(i-cur.d) == 2)
                        ntime = cur.time+2;
                    else
                        ntime = cur.time+1;
                    nd = i;
                    nr = cur.r;
                    nc = cur.c;
                    ncolor = cur.color;
                }
                if (maze[nr][nc] != '#' && !vis[nr][nc][ncolor][nd] && nr >=0 && nr < m && nc >=0 && nc < n)
                {
                    Node next = {nr, nc, ncolor, nd, ntime};
                    if (maze[nr][nc] == 'T' && ncolor == 0)
                    {
                            ans = ntime;
                            goto ret;
                    }
                    Q.push(next);
                }
            }
        }
        ret:
        if (kase != 1)
            puts("");
        printf("Case #%d\n", kase);
        kase++;
        if (ans == 0)
            printf("destination not reachable\n");
        else
            printf("minimum time = %d sec\n", ans);
    }
    return 0;
}

开始没做出来还是对BFS（搜索）认识不深刻，以后还需要多加练习。(。・・)ノ