만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

바다 전투

면접 대비

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

요약
n×m 격자에 놓인 배 k개가 주어질 때, 배가 겹치거나 닿으면 INCORRECT를 출력하고 아니면 새 1×1 배를 놓을 수 있는 칸의 수를 구합니다.
난이도

쉬움10점 중 3점

유형
행렬, 구현
정답자
아직 제출이 없습니다

문제

어린 얀은 바다 전투 게임의 인공지능을 작성하고 있습니다.

바다 전투는 두 명이 하는 게임입니다. 각 플레이어는 n×mn \times m 크기의 격자판에 여러 척의 배를 놓습니다. 각 배는 높이가 1인 가로 직사각형이거나 너비가 1인 세로 직사각형이며, 칸을 여러 개 차지합니다. 배들은 경계선을 포함해 어떤 점도 공유하면 안 됩니다.

게임의 어떤 시점에서 얀의 프로그램 모듈 하나는 적의 1×11 \times 1 배가 놓일 수 있는 위치의 수를 계산해야 합니다. 이 시점에는 다른 배 일부의 위치가 이미 알려져 있습니다. 상대가 배치 규칙을 어겼는지 확인하고, 어기지 않았다면 1×11 \times 1 배를 하나 더 놓을 수 있는 위치가 몇 곳인지 구합니다.

얀이 이 부분의 프로그램을 작성하도록 도와주세요.

입력

첫 줄에 세 정수 nn, mm, kk가 주어집니다 (1≤n,m≤10001 \le n, m \le 1000; 0≤k≤100000 \le k \le 10000). 각각 보드의 크기와 알려진 적 배의 개수입니다.

이후 kk개의 줄에는 각각 네 정수 x1x_1, y1y_1, x2x_2, y2y_2가 주어집니다 (1≤x1≤x2≤n1 \le x_1 \le x_2 \le n; 1≤y1≤y2≤m1 \le y_1 \le y_2 \le m). 배의 왼쪽 위 칸과 오른쪽 아래 칸의 좌표입니다.

배가 세로로 놓여 있으면 y1=y2y_1 = y_2이고, 가로로 놓여 있으면 x1=x2x_1 = x_2입니다.

출력

두 배가 서로 점을 공유하면(상대가 규칙을 어긴 경우) INCORRECT라는 단어만 출력합니다. 그렇지 않으면 1×11 \times 1 적의 배를 하나 더 놓을 수 있는 위치의 수를 정수로 출력합니다.

힌트

그림에서 점으로 표시된 칸이 첫 번째 예제에서 적의 1×11 \times 1 배가 놓일 수 있는 위치입니다.

예제2

  1. 예제 1

    입력
    10 10 10
    1 1 1 2
    1 4 3 4
    1 7 1 10
    3 1 6 1
    3 6 3 8
    3 10 4 10
    6 6 7 6
    8 1 8 2
    8 10 8 10
    10 6 10 10
    
    예상 출력
    17
    
  2. 예제 2

    입력
    3 3 2
    1 1 1 1
    2 2 2 3
    
    예상 출력
    INCORRECT