This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); i++)
typedef long long ll;
int H, W;
vector<string> grid;
vector<vector<bool>> visited; // bitset ?
vector<vector<ll>> dp;
priority_queue<vector<ll>> q;
void dfs(int hat, int wat, ll num)
{
//cerr << hat << " " << wat << " " << num << "\n";
if (visited[hat][wat]) return;
if (grid[hat][wat] == '.') return;
visited[hat][wat] = true;
dp[hat][wat] = num;
char ch = grid[hat][wat];
if (hat + 1 < H) if (grid[hat + 1][wat] == ch) q.push({-num, hat + 1, wat});
if (wat + 1 < W) if (grid[hat][wat + 1] == ch) q.push({-num, hat, wat + 1});
if (hat - 1 >= 0) if (grid[hat - 1][wat] == ch) q.push({-num, hat - 1, wat});
if (wat - 1 >= 0) if (grid[hat][wat - 1] == ch) q.push({-num, hat, wat - 1});
if (hat + 1 < H) if (grid[hat + 1][wat] != ch) q.push({-(num + 1), hat + 1, wat});
if (wat + 1 < W) if (grid[hat][wat + 1] != ch) q.push({-(num + 1), hat, wat + 1});
if (hat - 1 >= 0) if (grid[hat - 1][wat] != ch) q.push({-(num + 1), hat - 1, wat});
if (wat - 1 >= 0) if (grid[hat][wat - 1] != ch) q.push({-(num + 1), hat, wat - 1});
}
int32_t main()
{
cin>>H>>W;
grid.assign(H, "");
rep(i,0,H){
cin>>grid[i];
}
visited.assign(H, vector<bool>(W, false));
dp.assign(H, vector<ll>(W, 0));
q.push({-1,0,0});
while(!q.empty())
{
auto x = q.top();
q.pop();
dfs(x[1], x[2], -(x[0]));
}
ll ans = 1;
rep(i,0,H){
rep(j,0,W){
ans = max(ans, dp[i][j]);
//cerr << dp[i][j]<< " ";
}
//cerr << "\n";
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |