Submission #745788

#	Time	Username	Problem	Language	Result	Execution time	Memory
745788		darshitjn	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1268 ms	227584 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int,int>

int32_t main(){
    int n,m; cin >> n >> m;
    string s[n];
    for(int i=0; i<n; i++){
        cin >> s[i];
    }

    vector <pi> v = {{1,0},{0,1},{-1,0},{0,-1}};

    if(s[0][0]=='.'){cout << 0 << endl; return 0;}
    int ans = 1;
    vector <vector<bool>> vis(n,vector<bool>(m,0));
    vis[0][0] = 1;
    deque <pi> q;
    q.push_front({0,0});
    vector <vector<int>> d(n,vector<int>(m,0));
    d[0][0] = 1;
    function <bool(int,int)> ok = [&](int x,int y){
        if(x<0 || x>n-1 || y<0 || y>m-1){return false;}
        if(vis[x][y]){return false;}
        return (s[x][y] != '.');
    };

    function <void(pi)> process = [&](pi k){
        for(auto e:v){
            int x = e.first+k.first;
            int y = e.second+k.second;
            if(ok(x,y)){
                vis[x][y] = 1;
                d[x][y] = d[k.first][k.second];
                if(s[x][y] != s[k.first][k.second]){
                    q.push_back({x,y});
                    d[x][y]++;
                }else{
                    q.push_front({x,y});
                }
            }
        }
    };

    while(q.size()){
        auto k = q.front();
        q.pop_front();
        ans = max(ans,d[k.first][k.second]);
        process(k);
    }

    cout << ans << endl;
}

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