백준 BOJ 16920 C++ 확장 게임

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

int n, m, p, cnt;
int s[10], board[1002][1002];
bool visited[1002][1002];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void solve() {
    vector<queue<pair<int, int>>> players(10);
    cin >> n >> m >> p;
    for (int i = 1; i <= p; ++i) cin >> s[i];
    for (int i = 0; i < n; ++i) {
        string str;
        cin >> str;
        for (int j = 0; j < m; ++j) {
            if (str[j] == '#') {
                board[i][j] = -1;
                continue;
            }
            if (isdigit(str[j])) {
                board[i][j] = str[j] - '0';
                visited[i][j] = true;
                players[board[i][j]].push({i, j});
                continue;
            }
            cnt++;  // 확장 가능 횟수
        }
    }
    while (true) {
        bool is_extend = false;  // 벽에 갇혀서 확장 못하는 경우를 체크하기 위한 변수
        for (int i = 1; i <= p; ++i) {
            if (players[i].empty()) continue;  // 플레이어 큐 자체가 비어 있으면 반복문을 스킵
            for (int j = 0; j < s[i]; ++j) {
                int size = players[i].size();
                if (size == 0) break;  // 플레이어의 턴이 남아 있더라도 기물을 더 이상 확장할 수 없는 경우 종료
                while (size--) {
                    int x = players[i].front().first;
                    int y = players[i].front().second;
                    players[i].pop();
                    if (cnt == 0) {  // 보드를 전부 채운 경우 조기 종료
                        return;
                    }
                    for (int k = 0; k < 4; ++k) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                            if (board[nx][ny] == 0 && !visited[nx][ny]) {
                                visited[nx][ny] = true;
                                players[i].push({nx, ny});
                                board[nx][ny] = board[x][y];
                                cnt--;
                                is_extend = true;  // 확장
                            }
                        }
                    }
                }
            }
        }
        if (!is_extend) return;  // 모든 플레이어가 확장할 수 없는 경우 종료
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    int ans[10] = {0, };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (board[i][j] == -1) continue;
            ans[board[i][j]]++;
        }
    }
    for (int i = 1; i <= p; ++i) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
    return 0;
}