Submission #1187908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187908		versesrev	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	630 ms	42980 KiB

tracks

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <tuple>

int main() {
  int h, w;
  std::cin >> h >> w;
  std::vector<std::string> grid(h);
  for (auto& s : grid) std::cin >> s;
  
  int ans = 1;
  int dr[4] = {1, 0, -1, 0};
  int dc[4] = {0, 1, 0, -1};
  int cur = 0;
  std::deque<std::tuple<int, int>> que[2];
  std::vector<std::vector<bool>> vis(h, std::vector<bool>(w));
  que[cur].emplace_back(0, 0), vis[0][0] = true;
  while (not que[cur].empty() or not que[cur^1].empty()) {
    if (que[cur].empty()) {
      cur ^= 1, ++ans;
    }
    auto [r, c] = que[cur].front();
    que[cur].pop_front();
    for (int k = 0; k < 4; ++k) {
      int nr = r + dr[k];
      int nc = c + dc[k];
      if (nr < 0 or h <= nr
      or nc < 0 or w <= nc
      or vis[nr][nc]
      or '.' == grid[nr][nc]) continue;
      int nq = cur ^ (grid[nr][nc] != grid[r][c]);
      que[nq].emplace_back(nr, nc);
      vis[nr][nc] = true;
    }
  }
  std::cout << ans << "\n";
}

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