11559 Puyo Puyo

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

과거 뿌요뿌요라는 추억의 게임을 기억하는가? 상하좌우로 인접한 똑같은 종류의 블럭이 특정 개수가 넘으면 터지면서 콤보가 생기고 그 위의 모든 블럭들이 내려온다. 그것을 구현하는 문제이다. 매 단계마다 필드 전체를 훑으면서 DFS(Depth First Search)로 같은 블럭이 4개 이상 인접하는지 확인하고 있으면 콤보를 추가시켜주면서 다음 단계로 진행한다. dfs은 4개 이상인지 확인하는 함수이고 dfs2는 터질 블럭들을 표시하는 함수이다. 콤보가 진행된 후 해당 블럭의 열들의 모든 위의 블럭들을 내려줘야함을 유의하자. 이 동작은 move, move2에 해당한다. 더이상 콤보가 발생하지 않으면 콤보의 개수를 출력하고 종료해주면 된다.

#include <cstdio>
#include <cstring>
 
char f[12][7];
bool visit[12][6],visit2[12][6];
int cnt,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
 
void dfs(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0 || nx>=12 || ny<0 || ny>=6) continue;
        if(!visit[nx][ny] && f[nx][ny]==f[x][y])
            cnt++,visit[nx][ny]=true,dfs(nx,ny);
    }
}
 
void dfs2(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0 || nx>=12 || ny<0 || ny>=6) continue;
        if(!visit2[nx][ny] && f[nx][ny]==f[x][y])
            visit2[nx][ny]=true,dfs2(nx,ny);
    }
}
 
void move2(int x,int y)
{
    for(int i=x-1;i>=0;i--)
        f[i+1][y]=f[i][y];
    f[0][y]='.';
}
 
void move()
{
    for(int j=0;j<6;j++)
    {
        for(int i=0;i<12;i++)
        {
            if(visit2[i][j])
            {
                if(i==0) f[i][j]='.';
                else move2(i,j);
            }
        }
    }
}
 
void solve()
{
    int ans=0;
    while(true)
    {
        bool flag=false;
        for(int i=0;i<12;i++)
        {
            for(int j=0;j<6;j++)
            {
                if(f[i][j]!='.')
                {
                    cnt++,visit[i][j]=true,dfs(i,j);
                    if(cnt>=4) flag=true,visit2[i][j]=true,dfs2(i,j);
                    cnt=0;
                }
            }
        }
        if(!flag) break;
        move();
        ans++;
        memset(visit,0,sizeof(visit));
        memset(visit2,0,sizeof(visit2));
    }
    printf("%d\n",ans);
}
 
int main()
{
    for(int i=0;i<12;i++)
        scanf("%s",f[i]);
    solve();
    return 0;
}