Submission #639061

#	Time	Username	Problem	Language	Result	Execution time	Memory
639061		inksamurai	Tetris (COCI17_tetris)	C++17	80 / 80	1 ms	324 KiB

tetris

#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]);
	}
}

• Subtask 1: 80 / 80