#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3cSpNGp ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};
int main(){
_3cSpNGp;
int h,w;
cin>>h>>w;
vec(vec(char)) a(h,vec(char)(w));
rep(i,h)rep(j,w){
cin>>a[i][j];
}
vec(vi) color(h,vi(w,-1));
int cnt=0;
int b=0,t=0;
auto ok=[&](int x,int y)->bool{
return !(min(x,y)<0 or x>=h or y>=w);
};
auto dfs=[&](auto self,int x,int y)->void{
if(a[x][y]=='B') b=max(b,color[x][y]);
else t=max(t,color[x][y]);
rep(dir,4){
int nex=x+di[dir],ney=y+dj[dir];
if(ok(nex,ney)){
if(color[nex][ney]==-1 and a[nex][ney]==a[x][y]){
color[nex][ney]=color[x][y];
self(self,nex,ney);
}
}
}
return;
};
rep(i,h){
rep(j,w){
if(a[i][j]!='*' and color[i][j]==-1){
// cout<<i<<" "<<j<<"\n";
if(a[i][j]=='B' and b==0){
color[i][j]=cnt;
cnt++;
}else if(a[i][j]=='T' and t==0){
color[i][j]=cnt;
cnt++;
}else{
bool pok=0;
rep(dir,4){
int nei=i+di[dir],nej=j+dj[dir];
if(ok(nei,nej) and a[i][j]!='*' and a[i][j]!=a[nei][nej]){
if(color[nei][nej]!=-1 and color[nei][nej]<(a[i][j]=='B'?b:t)){
pok=1;
}
}
}
if(pok) color[i][j]=(a[i][j]=='B'?b:t);
else color[i][j]=cnt++;
}
dfs(dfs,i,j);
}
}
}
assert(cnt<=4);
cout<<cnt<<"\n";
//
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
