14671 영정이의 청소

특이한 형태로 퍼져나가는 곰팡이가 있을 때 맵 전체를 덮는 경우가 있는지 없는지 물어보는 문제다.

힌트 1. 시간제한이 없다.

이 말은 즉 특정 조건을 만족하면 무조건 맵을 덮는다는 뜻이다.

힌트 2. 2번 예

2번을 더 진행시켜 보면 이전에 덮었던 곳을 유지한 채 바깥으로 점점 확장한다.

2번 예에서 조금 다른 경우를 생각해보자. 체스판에서 같은 색에 속하지만 가로나 세로로 짝수만큼 차이나는 곳에 곰팡이가 존재할 경우

이렇게 주기적으로 빈 곳이 생긴다.

결론적으로 맵을 체스판으로 생각했을 때 각각의 색에 가로나 세로로 홀수만큼 차이나는 곳에 곰팡이가 모두 존재한다면

무조건 곰팡이가 맵을 모두 덮는다.

<코드>

#include<stdio.h>
int n, m, k, x, y;
bool c[2][2];
 
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (k--) {
        scanf("%d%d", &x, &y);
        c[(x + y) % 2][y % 2] = 1;
    }
    printf(c[0][0] & c[0][1] & c[1][0] & c[1][1] ? "YES\n" : "NO\n");
}