Submission #1265815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265815		thewizardman	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	335 ms	168444 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const pii dd[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int n, m, grid[4000][4000], dist[4000][4000], ans;
deque<pii> q;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  memset(dist, 0x3f, sizeof dist);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < m; j++) if (s[i] == 'F') grid[i][j] = 1; else if (s[i] == 'R') grid[i][j] = 2;
  }
  q.push_front({0, 0});
  dist[0][0] = 0;
  while (!q.empty()) {
    auto [x, y] = q.front(); q.pop_front();
    for (auto [dx, dy]: dd) {
      auto xx = x + dx, yy = y + dy;
      if (xx < 0 || yy < 0 || xx >= n || yy >= m || !grid[xx][yy]) continue;
      if (grid[x][y] == grid[xx][yy]) {
        if (dist[x][y] < dist[xx][yy]) {
          dist[xx][yy] = dist[x][y];
          q.push_front({xx, yy});
        }
      } else {
        if (dist[x][y] + 1 < dist[xx][yy]) {
          dist[xx][yy] = dist[x][y] + 1;
          q.push_back({xx, yy});
        }
      }
    }
  }
  for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (grid[i][j]) ans = max(ans, dist[i][j]);
  cout << ans+1;
}

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