어흥
[백준 16920] 확장 게임 (C++) 본문
728x90
반응형
문제 링크: www.acmicpc.net/problem/16920
1. 주의할 점
- BFS()를 통해 퍼트린다
- 최대한 간단하게 구현한다
2. 구현
- 한번에 퍼질 수 있는 정도를 Len[] 배열에 담는다
- 10개짜리 Queue를 생성하여 각 숫자에 해당하는 경우에만 포함하도록 한다
- 입력받을 때, 해당 지역이 성이면 개수를 센다
- BFS() 함수를 통해 1부터 P번까지의 Queue를 순서대로 퍼트린다
- Arr[][] 배열만을 사용하며, 다음 칸으로 이동이 가능하면 Arr[][] 배열을 바꾼다. 이 과정을 Queue 안의 원소수 * Len[]만큼 수행한다
- 모든 사람들이 퍼질때까지 위의 작업을 반복한다
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
int y, x;
};
info tmp;
int num, result, dig;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int row, col, p;
int area[10];
int len[10];
char arr[1000][1000];
queue<info> q[10];
void bfs() {
while (1) {
for (int t = 1; t <= p; t++) {
int dist = len[t];
while (!q[t].empty() && dist--) {
int qs = q[t].size();
for (int i = 0; i < qs; i++) {
int cx = q[t].front().x;
int cy = q[t].front().y;
q[t].pop();
for (int k = 0; k < 4; k++) {
int nx = cx + dx[k];
int ny = cy + dy[k];
if (nx >= 0 && ny >= 0 && nx < col && ny < row && arr[ny][nx] == '.') {
arr[ny][nx] = t + '0';
q[t].push({ ny,nx });
area[t]++;
}
}
}
}
}
bool finish = true;
for (int i = 1; i <= p; i++) {
if (!q[i].empty()) {
finish = false;
break;
}
}
if (finish) break;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> row >> col >> p;
for (int i = 1; i <= p; i++)
cin >> len[i];
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
cin >> arr[i][j];
if ('1' <= arr[i][j] && arr[i][j] <= '9') {
q[arr[i][j] - '0'].push({ i,j });
area[arr[i][j] - '0']++;
}
}
bfs();
for (int i = 1; i <= p; i++)
cout << area[i] << " ";
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 17142] 연구소 3 (C++) (0) | 2021.04.21 |
---|---|
[백준 17143] 낚시왕 (C++) (0) | 2021.04.21 |
[백준 20058] 마법사 상어와 파이어스톰 (C++) (0) | 2021.04.15 |
[백준 20057] 마법사 상어와 토네이도 (C++) (0) | 2021.04.14 |
[백준 5213] 과외맨 (C++) (0) | 2021.04.14 |
Comments