Submission #52088488

---

Source Code Expand

/**
 *  @the_hyp0cr1t3
 *  06.04.2024 17:42
**/
#include <bits/stdc++.h>

const std::pair<int, int> dirs[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> a(n);
    for (auto &x : a)
        std::cin >> x;

    int sx, sy, tx, ty;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'S')
                sx = i, sy = j;
            if (a[i][j] == 'T')
                tx = i, ty = j;
        }
    }

    auto bfs = [&](int rx, int ry) {
        std::vector d(n, std::vector<int>(m, -1));
        d[rx][ry] = 0;

        auto valid = [&](int x, int y) {
            return 0 <= x and x < n and 0 <= y and y < m and a[x][y] != '#';
        };

        std::vector<std::pair<int, int>> q;
        q.emplace_back(rx, ry);
        for (int i = 0; i < q.size(); i++) {
            auto [ux, uy] = q[i];
            for (auto [dx, dy] : dirs) {
                int vx = ux + dx, vy = uy + dy;
                if (valid(vx, vy) and d[vx][vy] == -1) {
                    d[vx][vy] = d[ux][uy] + 1;
                    q.emplace_back(vx, vy);
                }
            }
        }
        return d;
    };

    int start = -1;
    int q;
    std::cin >> q;
    std::vector<std::array<int, 3>> p(q);
    for (int it = 0; auto &[i, j, e] : p) {
        std::cin >> i >> j >> e;
        --i, --j;
        if (i == sx and j == sy)
            start = it;
        it++;
    }
    p.push_back({tx, ty, 0});
    q++;

    if (start == -1) {
        std::cout << "No" << '\n';
        return 0;
    }

    std::swap(p[0], p[start]);

    std::vector<std::vector<int>> g(q);
    for (int i = 0; i < q; i++) {
        auto [x, y, e] = p[i];
        auto d = bfs(x, y);
        for (int j = 0; j < q; j++) {
            auto [nx, ny, ne] = p[j];
            if (~d[nx][ny] and d[nx][ny] <= e)
                g[i].push_back(j);
        }
    }

    std::vector<int> vis(q);
    auto dfs = [&](auto &&self, int u) -> void {
        vis[u] = true;
        for (auto v : g[u])
            if (!vis[v]) self(self, v);
    };
    dfs(dfs, 0);

    std::cout << (vis[q - 1] ? "Yes" : "No") << '\n';
}

Submission Info

Compile Error

Main.cpp: In lambda function:
Main.cpp:38:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   38 |         for (int i = 0; i < q.size(); i++) {
      |                         ~~^~~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:62:16: warning: ‘ty’ may be used uninitialized [-Wmaybe-uninitialized]
   62 |     p.push_back({tx, ty, 0});
      |     ~~~~~~~~~~~^~~~~~~~~~~~~
Main.cpp:18:21: note: ‘ty’ was declared here
   18 |     int sx, sy, tx, ty;
      |                     ^~
Main.cpp:62:16: warning: ‘tx’ may be used uninitialized [-Wmaybe-uninitialized]
   62 |     p.push_back({tx, ty, 0});
      |     ~~~~~~~~~~~^~~~~~~~~~~~~
Main.cpp:18:17: note: ‘tx’ was declared here
   18 |     int sx, sy, tx, ty;
      |                 ^~
Main.cpp:58:21: warning: ‘sy’ may be used uninitialized [-Wmaybe-uninitialized]
   58 |         if (i == sx and j == sy)
      |             ~~~~~~~~^~~~~~~~~~~
Main.cpp:18:13: note: ‘sy’ was declared here
   18 |     int sx, sy, tx, ty;
      |             ^~
Main.cpp:58:9: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized]
   58 |         if (i == sx and j == sy)
      |         ^~
Main.cpp:18:9: note: ‘sx’ was declared here
   18 |     int sx, sy, tx, ty;
      |         ^~

Judge Result