톰 삼촌이 물려받은 땅

면접 대비

시간 제한1초메모리 제한128 MB

요약
최대 50칸만 사용할 수 있는 격자에서 사용 가능한 칸을 1x2 도미노로 최대 몇 개까지 덮을 수 있는지 구한다.
난이도

보통10점 중 7점

유형
그래프, 동적 계획법, 비트 연산, 구현
정답자
아직 제출이 없습니다

문제

당신의 나이 든 삼촌 톰은 고조부로부터 땅 한 필지를 물려받았습니다. 원래 이 땅은 직사각형 모양이었지만, 오래전 고조부는 땅을 단위 정사각형 격자로 나눈 뒤 일부 칸을 연못으로 만들었습니다. 오리 사냥을 좋아해 오리를 불러 모으고 싶었기 때문입니다. (연못을 너무 많이 파는 바람에, 남은 땅이 서로 떨어진 여러 개의 섬으로 나뉘어 있을 수도 있습니다.) 톰 삼촌은 이제 이 땅을 팔고 싶지만, 지역 규정이 매각 방식을 제한합니다.

규정에 따르면 땅은 정확히 단위 정사각형 두 칸 크기의 직사각형 구획(변을 맞댄 두 칸으로 이루어진 1×21\times2 또는 2×12\times1 구획)으로만 팔 수 있으며, 연못은 팔 수 없습니다. 톰 삼촌이 팔 수 있는 구획의 최대 개수를 구해 주세요. 팔리지 않고 남는 칸들은 모두 휴양 공원이 됩니다.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 땅의 행과 열의 수를 나타내는 두 정수 NN과 MM이 주어집니다 (1≤N,M≤1001 \le N, M \le 100). 둘째 줄에는 연못으로 바뀐 칸의 수 KK가 주어지며, (N×M)−K≤50(N \times M) - K \le 50을 만족합니다. 이어지는 KK개의 줄에는 각각 연못이 된 칸의 위치를 나타내는 두 정수 XX와 YY가 주어집니다 (1≤X≤N1 \le X \le N, 1≤Y≤M1 \le Y \le M). 입력의 끝은 N=M=0N = M = 0인 줄로 표시되며, 이 줄은 처리하지 않습니다.

출력

각 테스트 케이스마다 팔 수 있는 구획의 최대 개수를 나타내는 정수 하나를 한 줄에 출력합니다.

예제3

  1. 예제 1

    입력
    4 4
    6
    1 1
    1 4
    2 2
    4 1
    4 2
    4 4
    4 3
    4
    4 2
    3 2
    2 2
    3 1
    0 0
    
    예상 출력
    4
    3
    
  2. 예제 2

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

    입력
    2 2
    0
    0 0
    
    예상 출력
    2