바다 전투
면접 대비시간 제한2초메모리 제한1024 MB
n×m 격자에 놓인 배 k개가 주어질 때, 배가 겹치거나 닿으면 INCORRECT를 출력하고 아니면 새 1×1 배를 놓을 수 있는 칸의 수를 구합니다.
문제
어린 얀은 바다 전투 게임의 인공지능을 작성하고 있습니다.
바다 전투는 두 명이 하는 게임입니다. 각 플레이어는 크기의 격자판에 여러 척의 배를 놓습니다. 각 배는 높이가 1인 가로 직사각형이거나 너비가 1인 세로 직사각형이며, 칸을 여러 개 차지합니다. 배들은 경계선을 포함해 어떤 점도 공유하면 안 됩니다.

게임의 어떤 시점에서 얀의 프로그램 모듈 하나는 적의 배가 놓일 수 있는 위치의 수를 계산해야 합니다. 이 시점에는 다른 배 일부의 위치가 이미 알려져 있습니다. 상대가 배치 규칙을 어겼는지 확인하고, 어기지 않았다면 배를 하나 더 놓을 수 있는 위치가 몇 곳인지 구합니다.
얀이 이 부분의 프로그램을 작성하도록 도와주세요.
입력
첫 줄에 세 정수 , , 가 주어집니다 (; ). 각각 보드의 크기와 알려진 적 배의 개수입니다.
이후 개의 줄에는 각각 네 정수 , , , 가 주어집니다 (; ). 배의 왼쪽 위 칸과 오른쪽 아래 칸의 좌표입니다.
배가 세로로 놓여 있으면 이고, 가로로 놓여 있으면 입니다.
출력
두 배가 서로 점을 공유하면(상대가 규칙을 어긴 경우) INCORRECT라는 단어만 출력합니다. 그렇지 않으면 적의 배를 하나 더 놓을 수 있는 위치의 수를 정수로 출력합니다.
힌트
그림에서 점으로 표시된 칸이 첫 번째 예제에서 적의 배가 놓일 수 있는 위치입니다.