제출 #1001243

#제출 시각아이디문제언어결과실행 시간메모리
1001243vjudge3Tracks in the Snow (BOI13_tracks)C++17
97.81 / 100
1221 ms1048576 KiB
#include <bits/stdc++.h> using namespace std; bitset<4005> vis[4005], occ[4005], fox[4005]; vector<pair<short, short>> cur; int h, w, dep = 1; const int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; void dfs (short r, short c, bool f) { if (!vis[r][c]) cur.push_back({r, c}); vis[r][c] = true; for (int k = 0; k < 4; k++) { int rv = r + dr[k], cv = c + dc[k]; if (rv >= 1 && rv <= h && cv >= 1 && cv <= w && !vis[rv][cv] && occ[rv][cv] && fox[rv][cv] == f) dfs(rv, cv, f); } } int main () { cin >> h >> w; for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) { char ch; cin >> ch; if (ch != '.') occ[i][j] = true; if (ch == 'F') fox[i][j] = true; } dfs(1, 1, fox[1][1]); while (true) { vector<pair<short, short>> last; last.swap(cur); for (auto& [r, c] : last) dfs(r, c, (dep & 1) ^ fox[1][1]); last.clear(); if (cur.empty()) { cout << dep << '\n'; return 0; } dep++; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...