Submission #1185016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185016		Warinchai	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1073 ms	680148 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
string s[4005];
int ar[4005][4005];
int dis[4005][4005][2];
int inf=1e9;
int h,w;
struct node{
    int x,y,dis;
    int val;
    node(int _x=0,int _y=0,char _val=0,int _dis=0){
        x=_x,y=_y,val=_val,dis=_dis;
    }
};
deque<node>dq;
void go(int nh,int nw,node x){
    if(nh>=0&&nh<h&&nw>=0&&nw<w&&ar[nh][nw]!=2){
        if(ar[nh][nw]==ar[x.x][x.y])dq.push_front(node(nh,nw,ar[nh][nw],x.dis));
        else dq.push_back(node(nh,nw,ar[nh][nw],x.dis+1));
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>h>>w;
    for(int i=0;i<h;i++)cin>>s[i];
    for(int i=0;i<h;i++)for(int j=0;j<w;j++){
        if(s[i][j]=='F'){
            ar[i][j]=1;
        }else if(s[i][j]=='R'){
            ar[i][j]=0;
        }else{
            ar[i][j]=2;
        }
        dis[i][j][0]=dis[i][j][1]=inf;
    }
    dq.push_back(node(0,0,ar[0][0],1));
    int ans=0;
    while(!dq.empty()){
        node x=dq.front();
        dq.pop_front();
        if(x.dis>=dis[x.x][x.y][x.val])continue;
        dis[x.x][x.y][x.val]=x.dis;
        ans=max(ans,x.dis);
        int nh,nw;
        go(x.x+1,x.y,x);
        go(x.x-1,x.y,x);
        go(x.x,x.y+1,x);
        go(x.x,x.y-1,x);
    }
    cout<<ans;
}

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