아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

초콜릿

면접 대비

시간 제한2초메모리 제한512 MB

요약
도미노 조각으로 채워진 격자에서 조각을 자르지 않고 가로 또는 세로로 한 번에 나눌 수 있는지 판정한다.
난이도

보통10점 중 5점

유형
구현, 배열, 행렬, 완전 탐색
정답자
아직 제출이 없습니다

문제

페티야는 초콜릿을 아주 좋아한다. 마샤도 초콜릿을 아주 좋아한다. 얼마 전 페티야는 초콜릿 한 개를 샀고, 이제 마샤와 나눠 먹으려고 한다. 초콜릿은 n×mn \times m 크기의 직사각형이며, 작은 초콜릿 조각인 2×12 \times 1 직사각형들로 완전히 채워져 있다.

페티야는 초콜릿의 한 변과 평행한 어떤 직선을 따라 초콜릿을 부러뜨려 두 부분으로 나눈다. 페티야도 마샤도 부러진 조각을 좋아하지 않으므로, 페티야는 어떤 조각도 손상되지 않도록 초콜릿을 부러뜨리려고 한다.

페티야가 마샤와 초콜릿을 나눌 수 있도록 도와주자.

입력

첫째 줄에 두 정수 nn과 mm이 주어진다. (1≤n,m≤201 \le n, m \le 20; nn과 mm 중 적어도 하나는 짝수) 다음 nn개의 줄에는 각각 mm개의 수가 주어지며, 각 수는 해당 초콜릿 칸이 속한 조각의 번호이다. 조각의 번호는 11부터 n⋅m2\frac{n \cdot m}{2}까지이며, 서로 다른 두 조각이 같은 번호를 가지지 않는다.

출력

페티야가 조각을 손상시키지 않고 초콜릿을 부러뜨릴 수 있으면 <<Yes>>를, 아니면 <<No>>를 출력한다.

예제2

  1. 예제 1

    입력
    2 3
    1 1 2
    3 3 2
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    5 6
    1 2 2 3 3 4
    1 5 6 7 7 4
    8 5 6 9 10 10
    8 11 11 9 12 13
    14 14 15 15 12 13
    
    예상 출력
    No