11559번 Puyo Puyo

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

지난 번 풀이 : https://hsdevelopment.tistory.com/9 

좋은 문제여서, 다시 풀어보았다.

#include <bits/stdc++.h>
 
using namespace std;
 
char Map[13][7];
 
bool visit[13][7] = { false, };
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
vector<pair<int, int> > v;
 
int dfs(int r, int c, char color)
{
    int ret = 1;
 
    v.push_back({ r, c });
 
    visit[r][c] = true;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= 12 || x < 0 || x >= 6 || visit[y][x] || Map[y][x] != color) continue;
 
        ret += dfs(y, x, color);
    }
 
    return ret;
}
 
void update()
{
    for (int j = 0; j < 6; j++)
        for (int i = 11; i >= 0; i--)
        {
            if (Map[i][j] == '.') continue;
 
            int y = i;
 
            while (1)
            {
                ++y;
 
                if (Map[y][j] != '.')
                {
                    --y;
                    swap(Map[y][j], Map[i][j]);
                    break;
                }
 
                if (y >= 12) break;
            }
        }
}
 
int simulation()
{
    int ret = 0;
 
    while (1)
    {        
        bool stop = true;
 
        memset(visit, false, sizeof(visit));
 
        for (int i = 0; i < 12; i++)
            for (int j = 0; j < 6; j++)        
                if (Map[i][j] != '.' && !visit[i][j])
                {
                    if (dfs(i, j, Map[i][j]) >= 4)
                    {
                        stop = false;
                        for (auto a : v) Map[a.first][a.second] = '.';
                    }
 
                    v.clear();
                }
 
        if (!stop) update();                            
        else break;
 
        ++ret;
    }
    
    return ret;
}
 
int main(void)
{
    for (int i = 0; i < 12; i++) scanf("%s", Map[i]);
    
    printf("%d\n", simulation());
 
    return 0;
}