제출 #869510

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

tracks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 4000 + 7;
string s[N];
bool vis[N][N];
int dx[] = {+1, -1, 0, 0};
int dy[] = {0, 0, +1, -1};
int n, m, ret = 0;

void bfs(queue<pair<int, int>> &q1, queue<pair<int, int>> &q2, int d) {
  if (q1.empty()) return;
  ret = d;
  while (!q1.empty()) {
    pair<int, int> x = q1.front();
    q1.pop();
    for (int dir = 0; dir < 4; dir++) {
      if (x.first + dx[dir] < 0 || x.first + dx[dir] >= n || x.second + dy[dir] < 0 || x.second + dy[dir] >= m) {
        continue;
      }
      if (vis[x.first + dx[dir]][x.second + dy[dir]] == true || s[x.first + dx[dir]][x.second + dy[dir]] == '.') {
        continue;
      }
      vis[x.first + dx[dir]][x.second + dy[dir]] = 1;
      if (s[x.first + dx[dir]][x.second + dy[dir]] != s[x.first][x.second]) {
        q2.push({x.first + dx[dir], x.second + dy[dir]});
      } else {
        q1.push({x.first + dx[dir], x.second + dy[dir]});
      }
    }
  }
  bfs(q2, q1, d + 1);
}

int main() {
#ifdef ONPC
  freopen("input.txt", "r", stdin);
#endif // ONPC
#ifndef ONPC
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  queue<pair<int, int>> q1, q2;
  q1.push({0, 0});
  vis[0][0] = 1;
  bfs(q1, q2, 1);
  cout << ret << "\n";
  return 0;
}

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