Submission #1150007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150007		swayam78	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	476 ms	161032 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
 
/*
  #include<Luck>
  Compete against Yourself.
  Author - swayam_wish
*/
 
#define ll long long
#define pii pair<ll, ll>
#define piii pair<ll, pair<ll, ll>>
#define pis pair<int, string>
#define db double
int mod = 1e9+7;

ll gcd(ll a, ll b){
  if(min(a,b) == 0){
    return max(a,b);
  }
  if((a%b) == 0){
    return b;
  }
  return gcd(b,a%b);
 
}
 


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    t = 1;
 
 
    while(t--){
 
      int h , w;
      cin >> h >> w;
       
      vector<vector<char>> grid(h,vector<char>(w));

      for(int i = 0; i<h; i++){
         for(int j = 0; j<w; j++){
            cin >> grid[i][j];
         }
      }
      
     
      vector<vector<int>> vis(h,vector<int>(w,0));
      deque<pii> dq;

      dq.push_back({0,0});
      int delx[] = {0,0,1,-1};
      int dely[] = {1,-1,0,0};
      vis[0][0] = 1;
      
      int ans = 1;
     
      while(!dq.empty()){
         auto it = dq.front();
         dq.pop_front();

         int x = it.first;
         int y = it.second;
         int cost = vis[x][y];
         ans = max(ans,cost);

         for(int i = 0 ; i<4; i++){
            int cx = x + delx[i];
            int cy = y + dely[i];

            if(cx<0 || cy<0 || cx==h || cy==w || vis[cx][cy]!=0 || grid[cx][cy]=='.'){
               continue;
            }

            int wt = (grid[cx][cy] == grid[x][y]) ? 0 : 1;

            int tot = cost + wt;
            vis[cx][cy] = tot;

            if(wt){
               dq.push_back({cx,cy});
            }
            else{
               dq.push_front({cx,cy});
            }
         }

      }

      cout<<ans<<endl;

    
    }
}

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