2차원 컨베이어 벨트

농부 존의 우유 공장은 컨베이어 벨트가 놓인 칸들로 이루어진 \(N \times N\)(\(1 \le N \le 1000\)) 격자로 나타낼 수 있다. 위치 (\(a,b\))는 위에서 \(a\)번째 행, 왼쪽에서 \(b\)번째 열에 있는 칸을 나타낸다. 칸의 종류는 \(5\)가지이다.

1. "L" — 그 칸은 왼쪽을 향하는 컨베이어 벨트로, 매 시간 단위마다 그 위의 모든 물건을 왼쪽으로 1칸 옮긴다.
2. "R" — 그 칸은 오른쪽을 향하는 컨베이어 벨트로, 매 시간 단위마다 그 위의 모든 물건을 오른쪽으로 1칸 옮긴다.
3. "U" — 그 칸은 위쪽을 향하는 컨베이어 벨트로, 매 시간 단위마다 그 위의 모든 물건을 위로 1칸 옮긴다.
4. "D" — 그 칸은 아래쪽을 향하는 컨베이어 벨트로, 매 시간 단위마다 그 위의 모든 물건을 아래로 1칸 옮긴다.
5. "?" — 농부 존이 아직 그 칸에 컨베이어 벨트를 설치하지 않았다.

컨베이어 벨트는 물건을 격자 밖으로 옮길 수도 있음에 유의하자. 칸 \(c\)에 놓인 물건이 컨베이어 벨트 격자를 절대 벗어나지 못한다면 (즉, 격자 안에서 영원히 돌아다닌다면) 칸 \(c\)는 사용 불가능하다고 한다.

처음에 농부 존은 공장을 짓기 시작하지 않았으므로 모든 칸은 "?"로 시작한다. \(1\)일부터 \(Q\)일까지 \(Q\)(\(1 \le Q \le 2 \cdot 10^5\))일 동안, 농부 존은 매일 컨베이어 벨트가 없는 칸을 하나 골라 그 칸에 컨베이어 벨트를 설치한다.

구체적으로, \(i\)번째 날에 농부 존은 위치 (\(r_i,c_i\))(\(1 \le r_i,c_i \le N\))에 종류 \(t_i\)(\(t_i \in {\text{{L,R,U,D}}}\))의 컨베이어 벨트를 설치한다. 위치 (\(r_i,c_i\))에 컨베이어 벨트가 없음이 보장된다.

매일이 끝난 후, 컨베이어 벨트가 없는 나머지 모든 칸에 최적으로 컨베이어 벨트를 설치했을 때 달성할 수 있는 사용 불가능한 칸의 최소 개수를 찾도록 농부 존을 도와주자.

문제 제공: Alex Liang

배점

• 입력 4-5: \(N \le 10\)
• 입력 6-7: \(N \le 40\)
• 입력 8-13: 추가 제약 없음

문제 제공: Alex Liang

첫째 줄에 \(N\)과 \(Q\)가 주어진다.

다음 \(Q\)개의 줄 중 \(i\)번째 줄에 \(r_i\), \(c_i\), \(t_i\)가 순서대로 주어진다.

\(Q\)개의 줄을 출력한다. \(i\)번째 줄에는 현재 컨베이어 벨트가 없는 나머지 모든 칸에 농부 존이 최적으로 컨베이어 벨트를 설치했을 때의 사용 불가능한 칸의 최소 개수를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > December > Silver