시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB212906943.125%

문제

괴도 인하는 인하대학교의 수많은 동아리들이 두려워하는 악명 높은 도둑이다. 그는 동아리방에 남겨진 값비싼 물건들을 아무도 모르게 훔쳐 간다. 특이하게도 범행 전 늘 예고장을 보내지만, 워낙 신출귀몰한 탓에 모습이 목격된 적조차 없다.

IGRUS 동방의 보물 한정판 게임기 역시 괴도 인하의 눈을 피할 순 없었다. 범행 예고장을 받은 IGRUS 부원들은 게임기를 지키기 위해 동방에 다음과 같은 보안 시스템을 설치하였다.

  • 동방은 N × M의 직사각형 꼴이고, 입구는 왼쪽 위의 (1, 1) 위쪽에 존재한다.
  • 게임기와 보안 시스템을 끄는 스위치는 오른쪽 아래의 (N, M)에 있다.
  • K개의 감시 카메라를 설치한다. 각 감시 카메라는 (ai, bi)를 왼쪽 위, (ci, di)를 오른쪽 아래로 하는 직사각형 영역을 감시한다. 감시 영역에 누군가 감지되면 알람이 울린다.
  • 방 안에서 오른쪽 방향이나 아래쪽 방향이 아닌 다른 방향으로 움직이면 알람이 울린다. 대각선으로 움직여도 알람이 울린다.

다음 날 아침, 보안 시스템은 꺼져 있고 카메라 몇 개가 부서져 있었다. 물론 알람도 울리지 않았다. 부원들은 서둘러 게임기를 확인했지만 게임기 대신 쪽지 한 장 만이 남겨져 있었다.

감시 카메라들을 망가뜨려 미안합니다. 대신 알람을 울리지 않고 게임기를 가져가는데 필요한 최소한의 카메라만 부수었으니 금방 복구할 수 있겠죠? - 괴도 인하

IGRUS의 회장 여준이는 괴도 인하가 동방의 입구에서 출발해 오른쪽과 아래쪽으로만 이동해 보안 시스템을 끄는 스위치에 도달하기 위해 몇 개의 카메라를 부수었는지 궁금해졌다. 동방의 크기와 K개의 감시 카메라의 정보가 주어지면, 괴도 인하가 몇 개의 감시 카메라를 부수었는지 출력하는 프로그램을 작성해보자.

입력

첫 번째 줄에 괴도 인하가 지나가야 하는 방의 행의 개수와 열의 개수 NM이 주어진다.

두 번째 줄에 방에 존재하는 감시 카메라의 개수 K가 주어진다.

세 번째 줄부터 K개의 줄에 걸쳐 각 감시 카메라에 대해 감시 구역의 왼쪽 위 좌표 ai, bi와 오른쪽 아래 좌표 ci, di가 공백으로 구분되어 주어진다.

출력

주어진 방을 알람을 울리지 않고 통과하기 위해 괴도 인하가 부수어야 할 감시 카메라의 최솟값을 출력한다.

제한

  • 1 ≤ N, M ≤ 1,000
  • 1 ≤ K ≤ 2,000
  • 1 ≤ ai, ciN
  • 1 ≤ bi, diM
  • aici
  • bidi
  • 여러 개의 감시 카메라가 같은 감시 구역을 가질 수 있다.

예제 입력 1

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

예제 출력 1

1

다음 그림과 같은 경로로 움직이면 감시 카메라를 하나만 부수고 게임기를 훔칠 수 있다.

예제 입력 2

2 2
3
2 2 2 2
2 2 2 2
2 2 2 2

예제 출력 2

3

어떤 경로로 움직이든 3개의 감시 카메라를 부숴야 한다.

출처

University > 인하대학교 > 2022 IGRUS Newbie Programming Contest K번