#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |