Submission #1000994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000994		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	459 ms	138576 KiB

tracks

#include <bits/stdc++.h>
using i64 = long long;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

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

    int h, w;
    std::cin >> h >> w;
    
    std::vector<std::string> g(h);
    for (auto &s : g) {
        std::cin >> s;
    }

    std::vector dis(h, std::vector<int>(w));
    std::vector vis(h, std::vector<bool>(w));
    dis[0][0] = 0;

    std::deque<std::tuple<int, int>> q;
    q.push_back({0, 0});
    vis[0][0] = true;

    int ans = 0;
    while (q.size()) {
        auto [x, y] = q.front();
        q.pop_front();

        ans = std::max(ans, dis[x][y]);
        
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx < 0 || tx >= h || ty < 0 || ty >= w || vis[tx][ty]) {
                continue;
            }
            
            if (g[x][y] == g[tx][ty]) {
                dis[tx][ty] = dis[x][y];
                q.push_front({tx, ty});
            } else {
                dis[tx][ty] = dis[x][y] + 1;
                q.push_back({tx, ty});
            }
            vis[tx][ty] = true;
        }
    }
    std::cout << ans << "\n";

    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70