Submission #1176741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176741		julia_08	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	711 ms	174248 KiB

tracks

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

const int MAXN = 4e3 + 10;

char a[MAXN][MAXN];

int dist[MAXN][MAXN], marc[MAXN][MAXN];

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

int n, m;

bool check(int i, int j){
  return i > 0 && j > 0 && i <= n && j <= m && (a[i][j] != '.');
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      cin >> a[i][j];
    }
  }

  int ans = 0;

  deque<pair<int, int>> q;

  q.push_front({n, m}); dist[n][m] = 1; marc[n][m] = 1;

  while(!q.empty()){

    auto [i, j] = q.front(); q.pop_front();

    ans = max(ans, dist[i][j]);

    for(int k=0; k<4; k++){

      int ni = i + dx[k], nj = j + dy[k];

      if(check(ni, nj) && !marc[ni][nj]){

        marc[ni][nj] = 1;

        if(a[i][j] == a[ni][nj]){
          q.push_front({ni, nj});
          dist[ni][nj] = dist[i][j];

        } else{
          q.push_back({ni, nj});
          dist[ni][nj] = dist[i][j] + 1;

        }

      }

    }

  }

  cout << ans << "\n";

  return 0;
}

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