이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
this code written by :
shimutski_zoro
*/
#include <bits/stdc++.h>
using namespace std;
#define yon(x) cout<<((x)?"YES\n":"NO\n");
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define em emplace
#define emp emplace_back
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=k;i>=j;i--)
#define forp(x,y,a) for(auto &[x,y]:(a))
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;
typedef vector<vl> vvl;
typedef vector<vpl> vvpl;
typedef vector<string> vs;
typedef vector<set<ll> >vst;
typedef deque<ll> dl;
const int mod=1e9+7;
const ll inf =1e18+1;
const int N=1e6+1;
const ll dx[]={1,0,-1,0},dy[]={0,1,0,-1};
void solve(){
ll n,m;
cin>>n>>m;
vs g(n);
rep(i,0,n-1){
cin>>g[i];
}
vvl d(n,vl(m));
d[0][0]=1;
deque<pll>dq;
dq.emp(0,0);
auto is=[&](ll x,ll y){
return x>=0&&x<n&&y>=0&&y<m&&g[x][y]!='.';
};
ll ans=0;
while(!dq.empty()){
ll x=dq.front().ff,y=dq.front().ss;
ans=max(ans,d[x][y]);
dq.pop_front();
rep(i,0,3){
ll nx=x+dx[i],ny=y+dy[i];
if(is(nx,ny)&&!d[nx][ny]){
d[nx][ny]=d[x][y];
if(g[x][y]==g[nx][ny]){
dq.push_front({nx,ny});
}else{
d[nx][ny]++;
dq.push_back({nx,ny});
}
}
}
}
cout<<ans;
}
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef Usaco
string f="guard";
freopen((f+".in").c_str(),"r",stdin);
freopen((f+".out").c_str(),"w",stdout);
#endif
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}
/*
example:
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |