Submission #1213060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213060		i_love_spring	Tracks in the Snow (BOI13_tracks)	C++20	14.38 / 100	2100 ms	107712 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int inf = 1e9;
const int rc[]{0,0,1,-1};
const int cc[]{1,-1,0,0};
const int N = 4004;
char a[N][N];
int n,m, d[N][N];
void solve() {
  cin >> n >> m;
  int ok = 0, ok1 = 0;
  for (int i = 0; i < n;i++) {
    for (int j = 0; j < m;j++) {
      cin >> a[i][j];
    }
  }
  memset(d,-1,sizeof(d));
  deque<ar<int,2>> q;
  q.push_back({0,0});
  int ans = 0;
  d[0][0] = 1;
  while (!q.empty()) {
    auto [x,y] = q.front();
    q.pop_front();
    ans = max(ans,d[x][y]);
    for (int i = 0; i < n;i++) {
      int nx = rc[i] + x, ny = cc[i] + y;
      if (nx >= 0 && ny >= 0 && nx < n && ny < m && a[nx][ny] != '.') {
        if (d[nx][ny] == -1) {
          if (a[nx][ny] == a[x][y]) {
            d[nx][ny] = d[x][y];
            q.push_front({nx,ny});
          }else {
            d[nx][ny] = d[x][y] + 1;
            q.push_back({nx,ny});
          }
        }
      }
    }
  }
  cout << ans;
  
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
//  cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
} 

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