문제
정올국 광장에서는 자동 주행 택시를 시연할 예정이다.
광장은 n*m 격자판 모양의 직사각형 형태로 되어있으며,
각 행은 1부터 n까지, 각 열은 1부터 m까지 번호가 붙어 있다.
자동 주행 택시는 격자판의 각 칸 사이를 이동하며,
현재 위치한 칸에서 인접한 면이 존재하는 칸으로 단번에 이동할 수 있다.
올해 겨울은 눈이 많이 내려, 시연 기간 동안 무인 제설기를 이용하여 광장을 청소한다.
시연 내내 눈이 계속 내리자, 자동 주행 택시는 쌓인 눈을 극복하는 능력 또한 시연하기로 하였다.
각 격자판에 쌓인 눈의 깊이는 음이 아닌 정수로 나타낼 수 있다.
또한, 택시의 눈 극복력 또한 음이 아닌 정수로 주어진다.
택시는 이동 도중, 눈의 깊이가 택시의 눈 극복력을 넘지 않는 칸에만 있을 수 있다.
처음에는 모든 칸에 쌓인 눈의 깊이가 0이다.
매 시간이 시작할 때, 각 칸의 눈 깊이는 전부 1씩 증가한다.
이후, 세 가지 작업 중 하나가 수행된다.
각 작업에는 정확히 1시간이 걸린다.
1. 무인 제설기가 어떤 행을 청소하여, 해당 행의 모든 칸에 쌓인 눈의 깊이가 0이 된다.
2. 무인 제설기가 어떤 열을 청소하여, 해당 열의 모든 칸에 쌓인 눈의 깊이가 0이 된다.
3. 자동 주행 택시를 시연한다. 택시의 눈 극복력의 값을 설정하고, 시작 및 목적지 칸을 선택하고, 택시를 운행해 본다.
시작 칸부터 목적지 칸까지 모든 칸에 쌓인 눈의 높이가 택시의 눈 극복력 이하일 경우에만 택시가 해당 경로로 이동할 수 있다.
택시는 가장 짧은 경로로 이동한다.
각 3번 작업에 대하여, 택시 시연이 가능한지, 가능하다면 이동에 걸리는 가장 짧은 거리를 구하라.
입력
첫 번째 줄에는 n, m, q가 주어진다. 이 때, q는 시행하는 작업의 수이다.
이후 q개 줄에 걸쳐, 각 작업에 대한 설명이 주어진다.
- 1 r : 무인 제설기가 r번째 행을 청소한다.
- 2 c : 무인 제설기가 c번째 열을 청소한다.
- 3 r1 c1 r2 c2 k : 자동 주행 택시의 눈 극복력을 k로 설정하고, (r1, c1) 칸에서 (r2, c2) 칸으로 주행 시연한다.
출력
각 3번 작업에 대하여, 택시 시연이 가능하다면 이동에 걸리는 가장 짧은 거리를 각 줄에 출력하여라.
만약 택시 시연이 불가능하다면 -1을 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 19점 | n, m <= 50, q <= 4,000 |
| #2 | 20점 | n, m <= 10,000, q <= 10,000 |
| #3 | 19점 | n, m <= 1,000,000, q <= 10,000 |
| #4 | 10점 | n, m <= 100,000, q <= 100,000 |
| #5 | 10점 | n, m <= 1,000,000, q <= 300,000, 2번 작업이 주어지지 않는다. |
| #6 | 11점 | n, m <= 1,000,000, q <= 300,000, 모든 3번 작업에 대한 k가 전부 동일하다. |
| #7 | 11점 | n, m <= 1,000,000, q <= 300,000 |
예제
4 3 9
3 2 1 3 3 1
3 2 1 3 3 1
2 1
2 3
1 1
3 2 1 3 3 3
3 2 1 3 3 3
2 2
3 2 1 3 3 6
3
-1
5
-1
3
로그인해야 코드를 작성할 수 있어요.