Submission #1237542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237542		gramathegod	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	609 ms	121088 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

const int N=4e3+5;

int di[4]={1,-1,0,0};
int dj[4]={0,0,1,-1};

int n,m,ans;

int8_t v[N][N];

int check(int i, int j){
    return 0<=i && i<n && 0<=j && j<m && v[i][j]!=-1;
}

int d[N][N];

int main()
{
    memset(v, -1, sizeof(v));
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            char c;cin>>c;
            if (c=='F'){
                v[i][j]=1;
            }
            else if(c=='R'){
                v[i][j]=0;
            }
        }
    }
    deque<pair<int, int>>q;
    q.push_front({0,0});
    d[0][0]=1;
    while (!q.empty()){
        auto z=q.front();
        q.pop_front();
        int i=z.first;
        int j=z.second;
        ans=max(ans, d[i][j]);
        for (int k=0;k<4;k++){
            int newi=i+di[k];
            int newj=j+dj[k];
            if (check(newi, newj) && d[newi][newj]==0){
                if (v[i][j]==v[newi][newj]){
                    d[newi][newj]=d[i][j];
                    q.push_front({newi, newj});
                }
                else{
                    d[newi][newj]=d[i][j]+1;
                    q.push_back({newi, newj});
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

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