Submission #1266829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266829		marshziin	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	411 ms	117696 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>

const int maxn = 2100;
char g[maxn][maxn];
int vis[maxn][maxn], dist[maxn][maxn];

int dX[] = {0, 1, 0, -1};
int dY[] = {1, 0, -1, 0};

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int h, w; cin >> h >> w;
    for (int i = 1; i <= h; i++) 
        for (int j = 1; j <= w; j++) 
            cin >> g[i][j];
            

    deque<pii> dq;
    dq.push_front({1, 1});
    int ans = 0;
    while(!dq.empty()) {
        int x = dq.front().first, y = dq.front().second;
        dq.pop_front();
        vis[x][y] = true;
        ans = max(ans, dist[x][y]);

        for (int i = 0; i < 4; i++) {
            int curX = x + dX[i], curY = y + dY[i];
            if(curX < 1 || curX > h || curY < 1 || curY > w) continue;
            if(vis[curX][curY]) continue;
            

            if(g[curX][curY] == g[x][y]) {
                dq.push_front({curX, curY});
                dist[curX][curY] = dist[x][y];
            }
            else {
                dq.push_back({curX, curY}); 
                dist[curX][curY] = dist[x][y] + 1;
            }
        }
    }

    cout << ans << '\n';
}

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