제출 #1187916

#제출 시각아이디문제언어결과실행 시간메모리
1187916versesrevTracks in the Snow (BOI13_tracks)C++20
2.19 / 100
1520 ms45268 KiB
#include <iostream> #include <vector> #include <string> #include <queue> #include <tuple> #include <cassert> int main() { int h, w; std::cin >> h >> w; std::vector<std::string> grid(h); for (auto& s : grid) std::cin >> s; int ans = 0; int dr[4] = {1, 0, -1, 0}; int dc[4] = {0, 1, 0, -1}; std::priority_queue<std::tuple<int, int, int>> heap; std::vector<std::vector<bool>> vis(h, std::vector<bool>(w)); heap.emplace(0, 0, 0), vis[0][0] = true; while (not heap.empty()) { auto [d, r, c] = heap.top(); assert (ans == -d or ans-1 == -d); heap.pop(); 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 nd = d - (grid[nr][nc] != grid[r][c]); heap.emplace(nd, nr, nc); vis[nr][nc] = true; ans = std::max(ans, -d); } } std::cout << (ans + 1) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...