정올이의 정원은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 정원에는 총 K개의 스프링쿨러가 설치되어져 있는데, 스프링쿨러는 5가지 종류가 있다. 각 스프링쿨러가 감시할 수 있는 방법은 다음과 같다.

1번 스프링쿨러는 한 쪽 방향만 물을 뿌릴 수 있다. 2번과 3번은 두 방향으로 물을 뿌릴 수 있는데, 2번은 물 뿌리는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향으로 물을 뿌릴 수 있다.

스프링쿨러는 물을 뿌리는 방향에 있는 칸 전체에 물을 줄 수 있다. 정원에는 벽이 있는데, 스프링쿨러는 벽을 통과할 수 없다. 스프링클러로 물을 뿌릴 수 없는 영역은 사각지대라고 한다.

스프링쿨러는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 물을 뿌리는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0

0 0 0 0 0 0

0 0 1 0 6 0

0 0 0 0 0 0

지도에서 0은 빈 곳, 6은 벽, 1~5는 스프링쿨러의 번호이다. 위의 예시에서 1번의 방향에 따라 물을 뿌리는 영역을 '#'로 나타내면 아래와 같다.

0 0 0 0 0 0

0 0 0 0 0 0

0 0 1 # 6 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

# # 1 0 6 0

0 0 0 0 0 0

0 0 # 0 0 0

0 0 # 0 0 0

0 0 1 0 6 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 1 0 6 0

0 0 # 0 0 0

스프링쿨러는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 벽을 감시할 수 없다.

0 0 0 0 0 0

0 2 0 0 0 0

0 0 0 0 6 0

0 6 0 0 2 0

0 0 0 0 0 0

0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔

0 0 0 0 0 #

# 2 # # # #

0 0 0 0 6 #

0 6 # # 2 #

0 0 0 0 0 #

# # # # # 5

왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕

0 0 0 0 0 #

# 2 # # # #

0 0 0 0 6 #

0 6 0 0 2 #

0 0 0 0 # #

# # # # # 5

왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔

0 # 0 0 0 #

0 2 0 0 0 #

0 # 0 0 6 #

0 6 # # 2 #

0 0 0 0 0 #

# # # # # 5

왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕

0 # 0 0 0 #

0 2 0 0 0 #

0 # 0 0 6 #

0 6 0 0 2 #

0 0 0 0 # #

# # # # # 5

스프링쿨러는 스프링쿨러를 통과할 수 있다. 아래 예시를 보자.

2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3

0 6 # 0 #

0 0 6 6 #

0 0 0 0 #

정원의 크기와 상태, 그리고 스프링쿨러의 정보가 주어졌을 때, 스프링쿨러의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

#4204 upload 3 done 2 how_to_reg 2

[swat]감시 timer 2s memory 512MB

#4204

[swat]감시 2s 512MB