Submission #1208142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208142		timeflew	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	489 ms	118948 KiB

tracks

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

#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()

const int mxN=4e3;

int d[mxN][mxN], h, w;
char c[mxN][mxN];

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

bool check(int x, int y) {
    return (x>=0&&x<h&&y>=0&&y<w&&c[x][y]!='.');
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    d[0][0]=1;
    cin>>h>>w;
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            cin>>c[i][j];
        }
    }
    deque<pair<int, int>> dq;
    dq.push_back({0, 0});
    int ans=0;
    while(dq.size()) {
        auto [x, y]=dq.front();
        dq.pop_front();
        ans=max(ans, d[x][y]);
        // cout<<x<<' '<<y<<' '<<d[x][y]<<"\n";
        for(int i=0; i<4; i++) {
            int X=x+dx[i], Y=y+dy[i];
            if(check(X, Y)&&d[X][Y]==0) {
                if(c[X][Y]==c[x][y]) {
                    d[X][Y]=d[x][y];
                    dq.push_front({X, Y});
                } else {
                    d[X][Y]=d[x][y]+1;
                    dq.push_back({X, Y});
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

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