제출 #981038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981038		kilkuwu	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1238 ms	189532 KiB

tracks

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int N, M;
  std::cin >> N >> M;
  std::vector<std::string> s(N);
  for (int i = 0; i < N; i++) {
    std::cin >> s[i];
  }

  std::vector vis(N, std::vector<int>(M));
  auto nqg = vis;

  const std::vector<std::pair<int, int>> dxy = {
    {0, -1},
    {0, 1},
    {-1, 0},
    {1, 0}
  };

  auto valid = [&](int x, int y) {
    return 0 <= x && x < N && 0 <= y && y < M;
  };
  std::queue<std::pair<int, int>> q;
  q.push({0, 0});
  vis[0][0] = 1;
  int cnt =0 ;
  while (q.size()) {
    dbg(q);
    cnt++;
    std::vector<std::pair<int, int>> nq;
    while (q.size()) {
      auto [x, y] = q.front();
      q.pop();

      for (auto [dx, dy] : dxy) {
        int nx = x + dx, ny = y + dy;
        if (!valid(nx, ny)) continue;
        if (vis[nx][ny]) continue;
        if (s[nx][ny] == '.') continue;
        if (s[nx][ny] == s[x][y]) {
          q.emplace(nx, ny);
          vis[nx][ny] = 1;
        } else {
          if (nqg[nx][ny]) continue;
          nq.emplace_back(nx, ny);
          nqg[nx][ny] = 1;
        }
      }
    }

    std::queue<std::pair<int, int>> gg;
    for (auto [x, y] : nq) {
      vis[x][y] = 1;
      gg.emplace(x, y);
    }
    std::swap(gg, q);
  }

  std::cout << cnt << nl;
}

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