#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int h, w, f[4000][4000], a, b, res, x, y;
string s[4000];
bool check[4000][4000];
deque<pair<int, int>> dq;
int main()
{
setup();
cin >> h >> w;
for (int i = 0; i < h; ++i)
{
cin >> s[i];
for (int j = 0; j < w; ++j)
{
f[i][j] = 1e9;
}
}
dq.push_back({0, 0});
f[0][0] = 1;
while (!dq.empty())
{
a = dq.front().first;
b = dq.front().second;
dq.pop_front();
if (check[a][b])
{
continue;
}
check[a][b] = true;
res = max(res, f[a][b]);
for (int i = 0; i < 4; ++i)
{
x = a + dx[i];
y = b + dy[i];
if (0 <= x && x < h && 0 <= y && y < w && !check[x][y] && s[x][y] != '.')
{
if (f[x][y] > f[a][b] + (s[x][y] != s[a][b]))
{
f[x][y] = f[a][b] + (s[x][y] != s[a][b]);
if (s[x][y] != s[a][b])
{
dq.push_back({x, y});
}
else
{
dq.push_front({x, y});
}
}
}
}
}
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |