Submission #1289520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289520		bobtheguy	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	818 ms	173784 KiB

tracks

#include<bits/stdc++.h>
#define pll pair<int,int>
using namespace std;
 const int dx[4]={1,-1,0,0};
 const int dy[4]={0,0,-1,1};
 int a[4001][4001],cnt=0,x,y,h,w,i,j;
 char c;
 int d[4001][4001];
 bool visited[4001][4001];
 deque<pll> dq;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>h>>w;
    for (i=1;i<=h;i++){
        for (j=1;j<=w;j++){
            cin>>c;
            if (c=='R'){
                a[i][j]=1;
            }
            else if (c=='F'){
                a[i][j]=2;
            }
            else a[i][j]=0;
            d[i][j]=1e9;
        }
    }
    d[1][1]=0;
    dq.push_front({1,1});
    while (!dq.empty()){
        auto [i,j]=dq.front();
        dq.pop_front();
        if (visited[i][j]) continue;
        visited[i][j]=1;
        for (int k=0;k<4;k++){
            x=dx[k]+i;y=dy[k]+j;
            if (x<0||y<0||x>h||y>w) continue;
            if (a[i][j]==0||a[x][y]==0) continue;
            int w;
            if (a[i][j]==a[x][y]) w=0;
            else w=1;
            if (d[x][y]>d[i][j]+w){
                d[x][y]=d[i][j]+w;
                if (w==0) dq.push_front({x,y});
                else dq.push_back({x,y});
            }
        }
    }
    int ans=0;
    for (i=1;i<=h;i++){
        for (j=1;j<=w;j++){
            if (d[i][j]<1e9) ans=max(ans,d[i][j]);
        }
    }
    cout<<ans+1;
}

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