제출 #1283652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283652		VMaksimoski008	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	986 ms	119160 KiB

tracks

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

int dr[4] = { 1, -1, 0, 0 };
int dc[4] = { 0, 0, 1, -1 };

int n, m, dist[4005][4005];
char a[4005][4005];

signed main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) cin >> a[i][j];

    deque<pair<int, int> > q;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) dist[i][j] = 1e9;

    dist[1][1] = 0;
    q.push_front({ 1, 1 });

    int ans = 0;
    while(!q.empty()) {
        auto [r, c] = q.front(); q.pop_front();
        ans = max(ans, dist[r][c]);

        for(int i=0; i<4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(nr < 1 || nr > n || nc < 1 || nc > m) continue;
            if(a[nr][nc] == '.' || dist[nr][nc] != 1e9) continue;

            dist[nr][nc] = dist[r][c] + (a[r][c] != a[nr][nc]);
            if(dist[r][c] == dist[nr][nc])
                q.push_front({ nr, nc });
            else
                q.push_back({ nr, nc });
        }
    }
    
    cout << ans + 1 << '\n';
}

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