Submission #707951

#	Time	Username	Problem	Language	Result	Execution time	Memory
707951		spensa	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1214 ms	277680 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

int L[] = {0, 0, 1, -1};
int R[] = {1, -1, 0, 0};

const int MXN = 4020;
int arr[MXN][MXN] = {0};
int dist[MXN][MXN] = {0};
int vis[MXN][MXN] = {0};
int h, w;

bool check(int a, int b){
    if(a<1 || b<1 || a>h || b>w) return false;
    else return true;
}

int main(){
    //faster io
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>h>>w;
    string str;
    char c;
    int a, b, n1, n2, mx;


    for(int i=1; i<=h; i++){
        cin>>str;
        for(int j=1; j<=w; j++){
            c = str[j-1];
            if(c=='.') arr[i][j] = 0;
            else if(c=='R') arr[i][j] = 1;
            else arr[i][j] = 2;
        }
    }

    deque<pii> q;
    q.push_back({1,1});
    dist[1][1] = 1;

    while(!q.empty()){
        a = q.front().first;
        b = q.front().second;
        q.pop_front();

        for(int i=0; i<4; i++){
            n1 = a + L[i];
            n2 = b + R[i];
            if(!check(n1, n2)) continue;
            if(arr[n1][n2]==0) continue;
            if(vis[n1][n2]) continue;
            
            if(arr[a][b]==arr[n1][n2]){
                q.push_front({n1,n2});
                dist[n1][n2] = dist[a][b];
            }
            else{
                q.push_back({n1,n2});
                dist[n1][n2] = dist[a][b] + 1;
            }
                
        }

        vis[a][b] = 1;
    }

    mx = 0;

    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            // cout<<dist[i][j]<<" ";
            mx = max(mx, dist[i][j]);    
        }
        // cout<<"\n";
    }

    cout<<mx<<"\n";

}

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