1 条题解

  • 0
    @ 2024-8-10 20:35:36

    bfs  or  dijkstrabfs \; or \; dijkstra

    是板子 bfsbfs 或者 板子 dijkstradijkstra 。再满足一个题目要求,即:si,j>t+1s_{i,j} > t + 1tt 为你抵达 (i,j)(i,j) 的时间),这样你就可以通过这扇门。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    
    int main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int n, m;
        std::cin >> n >> m;
    
        std::vector s(n + 1, std::vector<int>(m + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                std::cin >> s[i][j];
            }
        }
    
        std::vector vis(n + 1, std::vector<int>(m + 1));
        std::queue<std::array<int, 3>> que;
        que.push({1, 1, 0});
        vis[1][1] = 1;
        while (not que.empty()) {
            auto [x, y, _] = que.front();
            que.pop();
            
            for (auto [dx, dy] : {std::array {1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
                int xx = x + dx, yy = y + dy;
                if (xx < 1 || yy < 1 || xx > n || yy > m || vis[xx][yy] || s[xx][yy] <= _ + 1) {
                    continue;
                }
    
                vis[xx][yy] = 1;
                que.push({xx, yy, _ + 1});
            }
        }
        std::cout << (vis[n][m] ? "Yes" : "No");
    
        return 0;
    }
    
    • 1

    信息

    ID
    43
    时间
    5000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    47
    已通过
    13
    上传者