제출 #725739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
725739		asdfgrace	Tracks in the Snow (BOI13_tracks)	C++17	20.83 / 100	631 ms	51416 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << endl)
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
using i64 = int64_t;
const int INF = 1000000007; //998244353

struct S {
  int n, m;
  array<array<char, 4000>, 4000> a{};
  array<array<bool, 4000>, 4000> visited{};

  void run() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        cin >> a[i][j];
      }
    }
  }
  
  void bfs() {
    deque<array<int, 3>> q; // {d, x, y}
    q.push_back({1, 0, 0});
    visited[0][0] = true;
    int ans = 1;
    while (!q.empty()) {
      int x = q.front()[1];
      int y = q.front()[2];
      int d = q.front()[0];
      q.pop_front();
      ans = max(ans, d);
      PV(x); PV(y); PV(d); PRINT('\n');
      char c = a[x][y];
      int a1 = ok(x, y + 1, c);
      if (a1 >= 0) {
        if (a1 == 1) q.push_back({d + 1, x, y + 1});
        else q.push_front({d, x, y + 1});
        visited[x][y + 1] = true;
      }
      int a2 = ok(x, y - 1, c);
      if (a2 >= 0) {
        if (a2 == 1) q.push_back({d + 1, x, y - 1});
        else q.push_front({d, x, y - 1});
        visited[x][y - 1] = true;
      }
      int a3 = ok(x + 1, y, c);
      if (a3 >= 0) {
        if (a3 == 1) q.push_back({d + 1, x + 1, y});
        else q.push_front({d, x + 1, y});
        visited[x + 1][y] = true;
      }
      int a4 = ok(x - 1, y, c);
      if (a4 >= 0) {
        if (a4 == 1) q.push_back({d + 1, x - 1, y});
        else q.push_front({d, x + 1, y});
        visited[x - 1][y] = true;
      }
    }
    cout << ans << '\n';
  }
  
  int ok(int x, int y, char c) {
    if (x < 0 || x >= n) return -1;
    if (y < 0 || y >= m) return -1;
    if (visited[x][y]) return -1;
    if (a[x][y] == '.') return -1;
    return (a[x][y] == c ? 0 : 1);
  }
  
  
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  auto sol = make_unique<S>();
  sol->run();
  sol->bfs();
}

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