페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8506
서브태스크

백신 1s 1024MB

문제

의료진은 최근 발생한 전염병 CV-19에 대한 백신을 테스트하고 있다.

의료진이 전자 현미경을 이용하여 인체 조직을 촬영하면 조직이 N행 M열의 격자 형태로 표현되고,
격자의 각 칸에는 해당 부분의 유전학적 성질에 해당하는 1 이상 1,000 이하의 정수 값이 부여된다.

인체 조직 중 하나의 칸에 백신을 놓으면 격자의 칸 중 하나에 항체가 생성된다.

이 항체는 현재 속해 있는 칸과 상하좌우로 인접하면서 같은 유전학적 성질을 가지는 칸이 있을 경우 그 칸으로 퍼진다.

이 과정을 계속 반복하다가 항체가 더 이상 퍼져나갈 수 없게 되면, 항체는 조직에 완전히 스며든다.

그 결과로 항체가 퍼졌던 칸들의 유전학적 성질 값이 모두 특정한 동일 값으로 새로 바뀐다.
이때,우연히 원래의 데이터 값과 업데이트된 데이터 값이 동일할 수도 있다.

의료진은 실험 자료를 정리하다가 두 개의 인체 조직 사진을 발견하였다.
의료진은 이 사진이 백신 테스트와 관련된 사진인지 검증해보려고 한다.

두 사진이 실험 전후 사진이 될 수 있는지 판별하는 프로그램을 작성하여라.

(a) 백신을 놓기 전

(b) 백신 투약

(c) 백신이 퍼지는 영역

(d) 백신이 퍼진 후

백신 투약 과정


입력

첫 번째 줄에는 인체 조직 촬영 결과의 크기를 의미하는 두 정수 N과 M이 주어진다.

(1 \le N, M \le 30) 이는 촬영 결과가 세로로 N칸, 가로로 M칸 크기의 격자라는 것을 의미한다.

다음 N개의 줄에는 첫 번째 사진의 정보가 주어진다.

각 줄에는 1 이상 1\,000 이하의 정수 M개가 공백으로 구분되어 주어지며,
i번째 줄의 j번째 수는 촬영 결과의 i번째 행 j번째 칸의 유전학적 성질 값을 의미한다.

다음 N개의 줄에는 두 번째 사진의 정보가 위와 동일한 형식으로 주어진다.


출력

첫 번째 사진이 실험 전 사진이고 두 번째 사진이 실험 후 사진일 수 있다면 YES 를, 그럴 수 없다면 NO 를 출력한다.


부분문제

번호 점수 조건
#112점

첫 번째 사진에서 모든 칸의 유전학적 성질 값이 서로 다르다.

#240점

첫 번째 사진에는 등장하지 않는 유전학적 성질 값이 두 번째 사진에 등장한다.

#332점

N = 1

#416점

추가 제약조건은 없다.


예제 #1

4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
4 4 4 1
4 4 1 3
4 1 3 3
1 3 3 3
YES

예제 #2

4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
YES

예제 #3

4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
2 2 2 1
2 2 2 3
2 1 3 3
1 3 3 3
YES

예제 #4

4 4
2 2 2 1
2 2 1 2
2 1 2 2
1 2 2 2
3 3 3 1
3 3 1 3
3 1 3 3
1 3 3 3
NO

예제 #5

3 5
1 1 1 3 3
1 1 2 3 3
1 1 2 2 4
1 1 1 4 4
1 1 2 4 4
1 1 2 2 4
YES


출처

UCPC 2021 예선 - B

로그인해야 코드를 작성할 수 있어요.