HDU 1312(BFS)

曾经终败给现在 2022-09-20 12:43 137阅读 0赞

题意：“.”是red方格，“\#”是black方格，“@”是起点。求从起点开始走，可以到达的方格（包括起点），red方格不能走，相当于墙壁。

#include <cstdio>
    #include <queue>
    #include <algorithm>
    using namespace std;
    
    char map[25][25];
    bool visit[25][25];
    int count;
    const int direction[4][2] = {
       {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    
    struct Node
    {
        int x, y;
        Node() {}
        Node(int _x, int _y) : x(_x), y(_y) {}
        Node next(int i)
        {
            return Node(x+direction[i][0], y+direction[i][1]);
        }
        bool visit()
        {
            return ::visit[x][y];
        }
        void set()
        {
            ++::count;
            ::visit[x][y] = true;
        }
        bool legal()
        {
            return map[x][y] != '#';
        }
    };
    
    int main()
    {
        int n, m, i, j, x, y;
        memset(map[0], '#', sizeof map[0]);
        while (scanf("%d%d", &m, &n) != EOF, n || m)
        {
            for (i = 1; i <= n; ++i)
                scanf("%s", map[i]+1), map[i][0] = map[i][m+1] = '#';
            memset(map[n+1], '#', sizeof map[0]);
            memset(visit, false, sizeof visit);
            for (i = 1; i <= n; ++i)
                for (j = 1; j <= m; ++j)
                    if (map[i][j] == '@')
                    {
                        x = i, y = j;
                    }
            ::count = 0;
            queue<Node> q;
            q.push(Node(x, y));
            Node(x, y).set();
            Node p, n;
            while (!q.empty())
            {
                p = q.front();
                q.pop();
                for (i = 0; i < 4; ++i)
                {
                    n = p.next(i);
                    if (!n.legal()) continue;
                    if (n.visit()) continue;
                    n.set();
                    q.push(n);
                }
            }
            printf("%d\n", ::count);
        }
        return 0;
    }