#include <bits/stdc++.h>
#define respagold ios_base::sync_with_stdio(0), cin.tie(0);
#define int long long
#define ll long long
#define int2 __int128_t
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define pb push_back
#define pf push_front
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define pii pair <int, int>
#define ppi pair <pair <int, int>, int>
#define pip pair <int, pair <int, int>>
#define mkp make_pair
using namespace std;
const int N = 4e3 + 12;
const int inf = 2e18;
const int mod = 1e9 + 7;
const double eps = 1e-20;
int n, m, x, y, k, used[N][N]; char a[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void solve()
{
cin >> n >> m;
FOR( i, 1, n, 1 )
{
FOR( j, 1, m, 1 ) cin >> a[i][j];
}
queue <pii> q[2];
q[0].push({1, 1});
int now = 0;
used[1][1] = 1;
while( !q[now].empty() )
{
x ++;
while( !q[now].empty() )
{
pii v = q[now].front();
q[now].pop();
FOR( i, 0, 3, 1 )
{
pii u = {v.F + dx[i], v.S + dy[i]};
if( u.F > n || u.S > m || min(u.F, u.S) < 1 || a[u.F][u.S] == '.' ) continue;
if( !used[u.F][u.S] )
{
if( a[u.F][u.S] == a[v.F][v.S] ) q[now].push(u);
else q[now ^ 1].push(u); used[u.F][u.S] = 1;
}
}
}
now ^= 1;
}
cout << x << '\n';
}
signed main()
{
respagold
int test = 1;
if( !test ) cin >> test;
while( test -- ) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |