Submission #1178178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178178		ritikthakur2712	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	653 ms	118968 KiB

tracks

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

int drow[4]{1, -1, 0, 0}, dcol[4]{0, 0, 1, -1};

int n, m, depth[4000][4000], ans = 1;
string snow[4000];
bool inside(int x, int y) {
	return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');
}
void solve(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>snow[i];
    }
    // todo: find the layers in the snow, like how deep can we go into the snow
    deque<pair<int,int>>q;
    q.push_back({0,0}); // top-left corner
    depth[0][0]=1;

    while(q.size()){
        pair<int,int>c = q.front();
        q.pop_front();
        ans = max(ans, depth[c.first][c.second]);

        for(int i=0;i<4; i++){
            int x = c.first + drow[i];
            int y = c.second + dcol[i];
            if( inside(x,y) && depth[x][y]==0 ){
                
                if ( snow[x][y] == snow[c.first][c.second] ){
                    depth[x][y] = depth[c.first][c.second];
                    q.push_front({x,y});
                }
                else{
                    depth[x][y] = depth[c.first][c.second] + 1;
                    q.push_back({x,y});
                }
            }
        }
    }
    cout<<ans<<"\n";
}
 
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
return 0;
}

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