Submission #1147477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147477		yeongminb	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	640 ms	119180 KiB

tracks

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
const int NMAX = 4e3;
const int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
typedef pair<int,int> pii;

int H,W, dist[NMAX + 10][NMAX + 10];
char meadow[NMAX + 10][NMAX + 10];

void solve(){
    deque<pii> q;
    q.push_back({0,0}); dist[0][0] = 0;
    while(!q.empty()){
        int x = q.back().first, y = q.back().second;
        q.pop_back();
        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
            if(meadow[nx][ny] == '.') continue;
            int w = (meadow[x][y] == meadow[nx][ny]) ? 0 : 1;
            if(dist[nx][ny] <= dist[x][y] + w) continue;
            dist[nx][ny] = dist[x][y] + w;
            if(w == 0) q.push_back({nx,ny});
            else q.push_front({nx,ny});
        }
    }
    
    int ans = 0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(meadow[i][j] == '.') continue;
            ans = max(ans, dist[i][j] + 1);
        }
    }
    cout << ans;
}

int main(){
    fastio;
    cin >> H >> W;
    for(int i=0;i<H;i++){
        string s; cin >> s;
        for(int j=0;j<W;j++){
            meadow[i][j] = s[j];
            dist[i][j] = 1e9;
        }
    }
    solve();
}

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