Submission #1218069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218069		nishchay213	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	659 ms	128020 KiB

tracks

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



int main() {
  int n, m;
  cin>>n>>m;
  vector<string> v(n);
  for (int i = 0; i<n; i++) cin>>v[i];
  vector<pair<int, int>> moves;
  moves.push_back({1,0});
  moves.push_back({0,1});
  moves.push_back({-1,0});
  moves.push_back({0,-1});
  vector<vector<int>> depth(n, vector<int> (m));
  deque<pair<int, int>> q;
  depth[0][0] = 1;
  int ans = 1;
  q.push_front({0, 0});
  while(!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop_front();
    ans = max(depth[x][y], ans);
    for (auto move: moves) {
      int new_x = x + move.first;
      int new_y = y + move.second;
      if (new_x<n && new_x>=0 && new_y<m && new_y>=0 && depth[new_x][new_y] == 0 && v[new_x][new_y] != '.') {
        if (v[new_x][new_y] == v[x][y]) {
          depth[new_x][new_y] = depth[x][y];
          q.push_front({new_x, new_y});
        }
        else {
          depth[new_x][new_y] = 1 + depth[x][y];
          q.push_back({new_x, new_y});
        }
      }
      
    }
  }
  cout<<ans;
}

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