Submission #707945

#	Time	Username	Problem	Language	Result	Execution time	Memory
707945		spensa	Tracks in the Snow (BOI13_tracks)	C++14	7.19 / 100	2151 ms	1048576 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++){
            for(int j=0; j<4; j++){
                n1 = a + L[i];
                n2 = b + R[j];
                if(check(n1, n2)){
                    if(arr[n1][n2]==0) continue;
                    if(!vis[n1][n2]){
                        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: 5 / 30
• Subtask 2: 2.1875 / 70