/*
Tracks_inthe_snow
Alone again
Telebe of adicto yani AzeTurk810
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#define MOD int(1e9 + 7)
int n , m;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
bool is_valid(int x , int y) {
return (x >= 0 && y >= 0 && x < n && y < n);
}
void solve() {
cin >> n >> m;
char c[n][m];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> c[i][j];
}
}
queue<pair<int,int>> q[2];
q[0].push({0 , 0});
vector<vector<bool>> used(n , vector<bool> (m , false));
int cur = 0;
int ans= 0;
while(!q[cur].empty()) {
ans++;
while(!q[cur].empty()) {
auto tt = q[cur].front();
q[cur].pop();
int x = tt.first , y = tt.second;
// cerr << x << ' ' << y<< ln;
for (int k = 0; k < 4; k++)
{
int cx = x + dx[k] , cy = y + dy[k];
if(!is_valid(cx , cy) || used[cx][cy] || c[cx][cy] == '.') continue;
// cerr << cx << ' ' << cy << ' ' << (c[x][y] == c[cx][cy]) << ln;
if(c[x][y] == c[cx][cy]) {
q[cur].push({cx , cy});
} else {
q[cur ^ 1].push({cx , cy});
}
used[cx][cy] = true;
}
}
cur ^= 1;
}
cout << ans << ln;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
}
//
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |