Submission #1237538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237538		gramathegod	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	1981 ms	1114112 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;
}

bool vis[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<tuple<int, int, int, int>>q;
    q.push_front(make_tuple(0,0,0,v[0][0]));
    while (!q.empty()){
        auto x=q.front();
        q.pop_front();
        int i=get<0>(x);
        int j=get<1>(x);
        int cd=get<2>(x);
        int animal=get<3>(x);
        ans=max(ans, cd+1);
        for (int k=0;k<4;k++){
            int newi=i+di[k];
            int newj=j+dj[k];
            if (check(newi, newj) && !vis[newi][newi]){
                if (animal==v[newi][newj]){
                    //same animal -> to the front of the queue
                    vis[newi][newj]=true;
                    q.push_front(make_tuple(newi, newj, cd, v[newi][newj]));
                }
                else{
                    //different animal -> to the back of the queue
                    vis[newi][newj]=true;
                    q.push_back(make_tuple(newi, newj, cd+1, v[newi][newj]));
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

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