11559 Puyo Puyo

https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

 

시뮬레이션에서 어려운 문제들을 많이 만나 기가 죽었었는데 이걸 풀면서 많이 나아진 것 같다. 크게 어려운 문제는 아니었다. 푸는데 45분정도 걸렸다. 개인적으로 재밌던 문제였다.

 

#include <bits/stdc++.h>
using namespace std;

string board[13];
int chain; //연쇄 횟수 
bool is_chain=true;
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
int vis[13][7];
queue<pair<int,int>> Q;

void gravity(){
	//터지고 나면 아래로 내려야됨 
	for(int i=0;i<6;i++){ //가로 
		char tmp[13];
		int idx=11;
		fill(tmp,tmp+13,'.');
		for(int j=11;j>=0;j--){ //세로 
			if(board[j][i]=='.') continue;
			tmp[idx--]=board[j][i];
		}
		for(int j=11;j>=0;j--){
			if(tmp[j]!=' '){
				board[j][i]=tmp[j];
			}
			else board[j][i]='.';
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	for(int i=0;i<12;i++){
		cin>>board[i];
	}
	
	while(is_chain){
		is_chain=false;
		for(int i=0;i<12;i++) fill(vis[i],vis[i]+7,false);
		
		for(int i=11;i>=0;i--){
			for(int j=5;j>=0;j--){
				if(vis[i][j]||board[i][j]=='.') continue;
				Q.push({i,j}); vis[i][j]=true;
				vector<pair<int,int>> tmp; //크기가 4 넘으면 값을 0으로 바꿈 
				tmp.push_back({i,j});
				while(!Q.empty()){
					auto cur=Q.front(); Q.pop();
					for(int dir=0;dir<4;dir++){
						int ny=cur.first+dy[dir];
						int nx=cur.second+dx[dir];
						if(nx<0||ny<0||nx>=6||ny>=12) continue;
						if(vis[ny][nx]||board[ny][nx]!=board[i][j]) continue;
						vis[ny][nx]=true; Q.push({ny,nx}); tmp.push_back({ny,nx});
					}
				}
				if(tmp.size()>=4){
					is_chain=true;
					for(int k=0;k<tmp.size();k++){
						int y=tmp[k].first; int x=tmp[k].second;
						board[y][x]='.';
					}
				}
			}
		}
		gravity();
		if(is_chain) chain++;
	}
	/*
	for(int i=0;i<12;i++){
		for(int j=0;j<6;j++){
			cout<<board[i][j]<<' ';
		}
		cout<<'\n';
	}
	*/
    cout<<chain<<'\n';
    return 0;
}