Submission #1185012

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

tracks

#include<bits/stdc++.h>
using namespace std;
string s[4005];
int ar[4005][4005];
int dis[4005][4005][2];
int inf=1e9;
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;
    }
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int h,w;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;
        }
        //cerr<<ar[i][j]<<" ";
        //if(j==w-1)cerr<<"\n";
        dis[i][j][0]=dis[i][j][1]=inf;
    }
    deque<node>dq;
    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;
        //cerr<<x.x<<" "<<x.y<<" "<<x.dis<<"\n";
        dis[x.x][x.y][x.val]=x.dis;
        ans=max(ans,x.dis);
        int nh,nw;
        nh=x.x+1,nw=x.y;
        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));
        }
        nh=x.x-1,nw=x.y;
        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));
        }
        nh=x.x,nw=x.y+1;
        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));
        }
        nh=x.x,nw=x.y-1;
        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));
        }
    }
    cout<<ans;
}

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