2920 : 여왕벌(고)
- 제한시간
- 5000 ms
- 메모리제한
- 512 MB
- 해결횟수
- 1 회
- 시도횟수
- 3 회
문제
크기가 M×M인 격자 형태의 벌집이 있다. 이 벌집의 각 칸에는 여왕벌이 될 애벌레들이 한 마리씩 자라고 있다.
격자칸의 좌표계를 다음과 같이 설정한다. 제일 왼쪽 위 칸의 좌표는 (0,0)이다.
애벌레들은 매일 에너지를 모아서 정오(낮 12시)에 한번 자라는데, 여기에 걸리는 시간은 매우 짧아서 무시할 수 있다.
각 애벌레가 자라서 크기가 커지는 정도는 하루에 +0, +1, +2의 세 가지 중 하나이다. 더하기(+) 기호는 앞으로 생략한다.
(1) 제일 왼쪽 열과, 제일 위쪽 행의 애벌레들은 자신이 자라는 정도를 스스로 결정한다. 이들은 입력으로 주어질 것이다.
(2) 나머지 애벌레들은 자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)의 애벌레들이 자라는 것을 완료한 후에,
(3) (2)에 해당하는 27가지 경우 각각에 대해서,
다음 페이지의 표 1은 4×4격자에 대한 애벌레 규칙의 예로, 16마리의 애벌레들 중,
예를 들어, 표 중앙의 회색 바탕의 칸에 있는 U의 의미에 대해 설명하면 다음과 같다. 좌표가 (2,1)인 칸에 있는 애벌레는,
M=4, N=2인 예를 하나 들어보자. 다음은 각 격자에 있는 애벌레의 첫날 아침의 크기이다.
다른 애벌레를 따라 자신이 자라는 정도를 결정하는 애벌레들의 규칙은 표 1과 같다.
처음 2일 동안 제일 왼쪽 열과 제일 위쪽 행에 있는 7마리의 애벌레들이 자라는 정도를 왼쪽 제일 아래 칸에서 시작하여 위쪽으로 가면서 읽고,
1일: 0, 0, 1, 1, 1, 2, 2
2일: 1, 1, 1, 1, 1, 1, 2
첫날 저녁에 애벌레들은 아래와 같은 크기를 가진다. 예를 들어, 좌표 (1,1)의 애벌레는 왼쪽 애벌레의 크기가 1만큼 자랐고,
왼쪽 위의 애벌레가 1만큼 자랐고, 위쪽 애벌레도 1만큼 자랐으므로, 표 1에 따라 왼쪽 애벌레가 자란 정도인 1만큼을 자란다.
또, 좌표 (3,2)의 애벌레는 규칙을 보면 1만큼 자람을 알 수 있다. 표 1에 방금 사용된 두 규칙을 동그라미가 쳐진 글자로 표시하였다.

둘째 날이 지났을 때는 동일한 과정에 따라 다음과 같이 됨을 확인할 수 있다.

격자칸의 크기, 날자 수, 애벌레들이 자라는 규칙과 날자별 제일 왼쪽 열과 제일 위쪽 행의 애벌레들이 자라는 정도를 입력으로 받아
입력형식
출력형식
표준 출력으로 다음을 출력한다.
M개의 줄에 각각 M개의 자연수를 출력한다.
이는 각 애벌레의 마지막 날 저녁의 크기를 첫 행부터, 각 행에서는 왼쪽부터 제시한 것이다. (본문의 예와 동일한 형태이다.)
부분문제의 제약 조건
• 부분문제 1: 전체 점수 100점 중 10점에 해당하며, N=1이다.
• 부분문제 2: 전체 점수 100점 중 24점에 해당하며, N≤10,000 이고 모든 날에 대해서 2의 개수가 0이다.
• 부분문제 3: 전체 점수 100점 중 34점에 해당하며, N≤10,000 이다.
• 부분문제 4: 전체 점수 100점 중 32점에 해당하며, 원래의 제약조건 이외의 아무 제약 조건이 없다.
입력 예2 3 UDLLDUDLLLLDULDUUUDDDLLLDDD 1 1 1 0 3 0 0 0 3 |
출력 예5 6 4 6 |
입력 예4 2 LLLLLLLLLLLLLLLLLLLLLLLLLLL UDLUDLUDLUDLUDLUDLUDLUDLUDL LDUUDDDLLDLLLLDDDDUUUDDDLLL DDLUUDLLDLDDUDLDDDDLDDDDLDD DDLLULDDDLLLLDDUULLUUULUUUL LLLLUUULLLLUUUUDDLDUDLLLUDU LLDDUULLLUUULDDUUULDUUULDUU DDDDDDDDDDDDDDDDDDDDDDDDDDD UUUUUUUUUUUUUUUUUUUUUUUUUUU 2 3 2 0 6 1 |
출력 예3 3 4 5 3 3 3 4 2 3 3 4 2 2 3 4 |