16920번 확장 게임

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

1부터 숫자들의 위치를 저장하고, bfs를 갈 수 있는 거리만큼 실행한다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 1010
 
int n, m, p, path[Max], answer[Max];
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
char Map[Max][Max];
bool visit[Max][Max];
queue<pair<int, int> > q[Max];
 
void bfs()
{
    while (1)
    {
        bool stop = true;
 
        // 1부터 차례대로
        for (int num = 1; num <= p; num++) {
 
            // 얼마만큼 가는지
            int len = path[num];
 
            // 비어있지 않고, 길이만큼만 간다
            while (!q[num].empty() && len--)
            {
                int qs = q[num].size();
 
                while (qs--)
                {
                    int r = q[num].front().first;
                    int c = q[num].front().second;
 
                    q[num].pop();
 
                    for (int i = 0; i < 4; i++) {
                        int y = r + dy[i];
                        int x = c + dx[i];
 
                        if (y < 0 || y >= n || x < 0 || x >= m || visit[y][x] || Map[y][x] != '.') {
                            continue;
                        }
 
                        stop = false;
                        ++answer[num]; // 계산
                        visit[y][x] = true;
                        q[num].push({ y, x });
                    }
                }
            }
        }
 
        // 더 이상 진행하지 않아도 되면, 탈출
        if (stop) {
            break;
        }
    }
}
 
int main()
{
    cin.tie(0);
    scanf("%d %d %d", &n, &m, &p);
    
    for (int i = 1; i <= p; i++) {
        scanf("%d", &path[i]);
    }
 
    for (int i = 0; i < n; i++) {
        scanf("%s", &Map[i][0]);
        for (int j = 0; j < m; j++) {
            if (Map[i][j] != '.' && Map[i][j] != '#') {
                q[Map[i][j] - '0'].push({ i, j });
                visit[i][j] = true;
                ++answer[Map[i][j] - '0'];
            }
        }
    }
 
    bfs();
 
    for (int i = 1; i <= p; i++) {
        printf("%d ", answer[i]);
    }
 
    printf("\n");
 
    return 0;
}