Submission #1154003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154003		Newtonabc	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	463 ms	42120 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
const int N=4010;
int a[4]={0,0,1,-1};
int b[4]={1,-1,0,0};
vector<string> v;
bool vs[N][N];
queue<pair<int,int>> qf,qr;
bool now;
//false=qf , true=qr
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n >>m;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        v.push_back(s);
    }
    if(v[0][0]!='F') now=true;
    if(now) qr.push({0,0});
    else qf.push({0,0});
    vs[0][0]=true;
    int ans=0;
    while(!(qf.empty() && qr.empty())){
        ans++;
        if(!now){
            //floodfill of f
            while(!qf.empty()){
                auto [x,y]=qf.front();
                qf.pop();
                for(int i=0;i<4;i++){
                    int xa=x+a[i],yb=y+b[i];
                    if(xa<0 || xa>=n || yb<0 || yb>=m) continue;
                    if(vs[xa][yb] || v[xa][yb]=='.') continue;
                    if(v[xa][yb]=='R'){
                        vs[xa][yb]=true;
                        qr.push({xa,yb});
                        continue;
                    }
                    vs[xa][yb]=true;
                    qf.push({xa,yb});
                }
            }
            now=true;
        }
        else{
            //floodfill of r
            while(!qr.empty()){
                auto [x,y]=qr.front();
                qr.pop();
                for(int i=0;i<4;i++){
                    int xa=x+a[i],yb=y+b[i];
                    if(xa<0 || xa>=n || yb<0 || yb>=m) continue;
                    if(vs[xa][yb] || v[xa][yb]=='.') continue;
                    if(v[xa][yb]=='F'){
                        vs[xa][yb]=true;
                        qf.push({xa,yb});
                        continue;
                    }
                    vs[xa][yb]=true;
                    qr.push({xa,yb});
                }
            }
            now=false;
        }
        // for(int i=0;i<n;i++){
        //     for(int j=0;j<m;j++){
        //         cout<<vs[i][j];
        //     }
        //     cout<<"\n";
        // }
        // cout<<"\n";
    }
    cout<<ans;
}

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