Submission #1097499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097499		jaintanmayp	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	811 ms	250852 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
// #define ll double
#define vl vector<ll>
#define vpll vector<pair<ll,ll>>
#define vvl vector<vector<ll>> 
#define vvc vector<vector<char>> 
#define newl cout << endl;
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl; 


const ll N = 4*(1e3) + 2;
// vvl adj(N);
vector<string> field(N);

// vector<ll> vis(N,0);
ll n, m;

ll dr[4] = {+1, 0, 0, -1};
ll dc[4] = {0, -1, +1, 0};

bool check(ll r, ll c){
    if(r < 0 || r >= n) return false;
    if(c < 0 || c >= m) return false;
    if(field[r][c] == '.') return false;
    
    return true;
}

void solve(){
 
    cin >> n >> m;
    
    for(ll i = 0; i < n; i++){
        cin >> field[i];
    }
    
    deque<pair<ll,ll>> q;
    vvl dist(n, vl(m, -1));
    q.push_back({0,0});
    dist[0][0] = 1;
    
    ll ans = 1;
    
    while(!q.empty()){
        auto it =  q.front();
        q.pop_front();
        ll r  = it.first;
        ll c =  it.second;

        
        for(ll i = 0; i < 4; i++){
            ll nr = r + dr[i];
            ll nc = c + dc[i];
            
            ans = max(ans , dist[r][c]);
            if(!check(nr, nc)) continue;
            
            if(dist[nr][nc] == -1){
                if(field[r][c] == field[nr][nc]){
                    dist[nr][nc] = dist[r][c];
                    q.push_front({nr, nc});
                }
                else{
                    dist[nr][nc] = dist[r][c] + 1;
                    q.push_back({nr, nc});
                    // ans++;
                }
            }
            
        }
        
    }
    

    cout << ans << endl;
    
    
    return;
 
}
 
int main(){
    
    ll t=1;
    // cin>>t;
    while(t>0){
        solve();
        t--;
    }
    
    
    return 0;
}

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