#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3RhsN1z ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
signed main(){
_3RhsN1z;
int h,w;
cin>>h>>w;
vec(string) a(h);
rep(i,h){
cin>>a[i];
}
vi cnt(5);
vec(vec(string)) figures={
{"aa",
"aa"},
{"aaaa"},
{".aa",
"aa."},
{"aa.",
".aa"},
{".a.",
"aaa"}
};
auto rotate=[&](vec(string) grid){
int h=sz(grid),w=sz(grid[0]);
vec(string) negrid(w,string(h,'.'));
rep(i,h){
rep(j,w){
negrid[j][h-1-i]=grid[i][j];
}
}
return negrid;
};
auto match=[&](int i,vec(string) grid){
rep(_,4){
if(grid==figures[i]){
return true;
}
grid=rotate(grid);
}
return false;
};
vec(vi) usd(h,vi(w));
auto ok=[&](int x,int y)->bool{
return min(x,y)>=0 and x<h and y<w;
};
auto bfs=[&](int sx,int sy){
queue<pii> que;
usd[sx][sy]=1;
que.push(pii(sx,sy));
vec(pii) delay;
while(sz(que)){
pii top=que.front();
que.pop();
int i=top.fi,j=top.se;
delay.pb(pii(i,j));
rng(di,-1,2){
rng(dj,-1,2){
int ni=i+di,nj=j+dj;
if(ok(ni,nj)){
if(!usd[ni][nj] and a[ni][nj]==a[sx][sy]){
usd[ni][nj]=1;
que.push(pii(ni,nj));
}
}
}
}
}
pii xs={h,0},ys={w,0};
//mi,ma
for(auto p:delay){
xs.fi=min(xs.fi,p.fi);
xs.se=max(xs.se,p.fi);
ys.fi=min(ys.fi,p.se);
ys.se=max(ys.se,p.se);
}
int n=xs.se-xs.fi+1,m=ys.se-ys.fi+1;
vec(string) grid(n,string(m,'.'));
rng(i,xs.fi,xs.se+1){
rng(j,ys.fi,ys.se+1){
if(a[i][j]==a[sx][sy]){
grid[i-xs.fi][j-ys.fi]='a';
}
}
}
rep(i,5){
cnt[i]+=match(i,grid);
}
};
rep(i,h){
rep(j,w){
if(!usd[i][j] and a[i][j]!='.'){
bfs(i,j);
}
}
}
rep(i,5){
print(cnt[i]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Correct |
0 ms |
324 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
320 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
