#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 1000
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;
void solve(){
int n,m;
cin >> n >> m;
char a[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin >> a[i][j];
priority_queue<tiii,vector<tiii>,greater<tiii>> pq;
pq.push({1,0,0});
int d[n][m],ans=0;
memset(d,-1,sizeof(d));
while(!pq.empty()){
int x,y,val;
tie(val,x,y)=pq.top();
pq.pop();
if(d[x][y]!=-1) continue;
d[x][y]=val;
ans=max(ans,val);
if(x!=n-1 && a[x+1][y]!='.' && d[x+1][y]==-1)
pq.push({val+(a[x+1][y]!=a[x][y]),x+1,y});
if(x!=0 && a[x-1][y]!='.' && d[x-1][y]==-1)
pq.push({val+(a[x-1][y]!=a[x][y]),x-1,y});
if(y!=m-1 && a[x][y+1]!='.' && d[x][y+1]==-1)
pq.push({val+(a[x][y+1]!=a[x][y]),x,y+1});
if(y!=0 && a[x][y-1]!='.' && d[x][y-1]==-1)
pq.push({val+(a[x][y-1]!=a[x][y]),x,y-1});
}
cout << ans << endl;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;
//~ cin >> test;
while(test--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |