Submission #492544

#	Time	Username	Problem	Language	Result	Execution time	Memory
492544		Shaurya_Bhalla	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	835 ms	141552 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define inin int
#define vi vector<int> 
#define all(x) x.begin(), x.end()

/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

const inin N=1e3+2, M=3e5+10, mod=1e9+7;

bool com(vector<int> a, vector<int> b){
    return abs(a[1]-a[0])<abs(b[1]-b[0]);
}

vector<int> mx = {1, -1, 0, 0}, my = {0, 0, 1, -1};

int h, w;
const int n = 4010;
vector<vector<char>> a(n, vector<char>(n, '.'));
vector<vector<int>> depth(n, vector<int>(n, 0));

bool isinside(int x, int y){
    return (x>=0 && y>=0 && x<h && y<w && a[x][y]!='.');
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);  
    
    cout<<setprecision(15)<<fixed;

    cin>>h>>w;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin>>a[i][j];
        }
    }

    deque<pair<int, int>> d;
    d.push_back({0, 0});
    depth[0][0] = 1;
    int ans = 0;
    while(!d.empty()){
        int x = d.front().first, y = d.front().second;
        d.pop_front();
        ans = max(ans, depth[x][y]);
        for(int i=0; i<4; i++){
            int xn = x+mx[i], yn = y+my[i];
            if(isinside(xn, yn) && depth[xn][yn] == 0){
                if(a[x][y] == a[xn][yn]){
                    depth[xn][yn] = depth[x][y];
                    d.push_front({xn, yn});
                }else{
                    depth[xn][yn] = depth[x][y]+1;
                    d.push_back({xn, yn});
                }
            }
        }
    }

    cout<<ans<<endl;
}

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