곰팡이는 4방향의 대각선으로 증식하고 현재위치는 없어지는 방식으로 퍼진다.
곰팡이가 모든 방에 증식되는 시점이 있는지 여부를 구하는 문제이다.
bfs로 홀수 시점, 짝수 시점으로 나누어 탐색시켰다.
탐색 후 홀수 시점이나 짝수 시점으로 판단할 수 있다.
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int N, M, P;
bool v1[1001][1001], v2[1001][1001];
int dy[] = { -1,1,-1,1 };
int dx[] = { -1,1,1,-1 };
int x, y;
bool chk(int y, int x) {
if (y < 0 || y >= N || x < 0 || x >= M) return false;
return true;
}
int main() {
scanf("%d%d%d", &N, &M, &P);
for (int p = 0;p < P;p++) {
scanf("%d%d", &y, &x);
x--; y--;
if (!v1[y][x]) {
queue<pair<pair<int, int>, int>> q;
v1[y][x] = true;
q.push({ { y,x }, 0 });
while (!q.empty()) {
int iy = q.front().first.first, ix = q.front().first.second;
int f = q.front().second;
q.pop();
for (int i = 0;i < 4;i++) {
int ny = iy + dy[i], nx = ix + dx[i];
if (chk(ny, nx) && !f && !v2[ny][nx]) {
v2[ny][nx] = true;
q.push({ { ny,nx }, 1 });
}
else if (chk(ny, nx) && f && !v1[ny][nx]) {
v1[ny][nx] = true;
q.push({ {ny,nx},0 });
}
}
}
}
}
int a = 0, b = 0;
for (int n = 0;n < N;n++) for (int m = 0;m < M;m++) {
a += v1[n][m];
b += v2[n][m];
}
if (a == N*M || b == N*M) printf("YES\n");
else printf("NO\n");
return 0;
}
| cs |
더 간단한 방법이 존재한다.
곰팡이는 동일한 시점에 대각선 2칸거리만큼 증식된다.
이것을 이용하면 2X2의 지도를 채울 수 있는지 여부를 판단하는것이 답을 구하는것과 같다.
#include <cstdio>
int N, M, P;
int map[2][2];
int main() {
scanf("%d%d%d", &N, &M, &P);
for (int p = 0;p < P;p++) {
int x, y;
scanf("%d%d", &y, &x);
y--, x--;
map[y & 1][x & 1] = 1;
}
int ans = 1;
for (int n = 0;n < 2;n++)for (int m = 0;m < 2;m++)
ans &= map[n][m];
printf("%s\n", ans ? "YES" : "NO");
return 0;
}
| cs |
댓글 없음:
댓글 쓰기