웜뱃(wombats) timer 20초 memory 256MB

브리즈번 시는 돌연변이로 거대해진 웜뱃(호주에 사는 너구리 비슷한 동물)에 장악당했다. 

당신의 임무는 사람들을 구조하는 것이다.

브리즈번 시의 도로는 커다란 격자 모양으로 되어 있다.

동서 방향으로 놓인 수평도로는 R 개가 있고, 북쪽에서 남쪽 방향으로 차례로 번호가 0, …, (R - 1) 로 매겨져 있다. 

또한, 남북 방향으로 놓인 수직도로는 C 개가 있고, 서쪽에서 동쪽 방향으로 차례로 번호가 0, …, (C - 1) 로 매겨져 있다. 

다음 그림은 이렇게 번호가 매겨진 도로의 예이다.

웜뱃은 북쪽에서부터 쳐들어오고 있고, 사람들은 남쪽으로 도망친다. 

사람들은 가로 방향으로는 어느 쪽이든 움직일 수 있지만, 세로 방향으로는 안전한 방향인 남쪽으로만 움직일 수 있다.

수평 도로 P 와 수직 도로 Q 의 교차로는 (P, Q) 로 표현한다. 

두 교차로 사이 세그먼트에는 웜뱃들이 있을 수 있고, 몇 마리의 웜뱃이 있는지는 시간이 흐르면서 변할 수 있다.

여러분의 임무는 북쪽(수평 도로 0 번)의 주어진 교차로에 도착한 사람을 

남쪽(수평 도로 R - 1 번)의 주어진 교차로로 가는 길을 알려주는 것인데, 이 경로를 지날 때 가능한 한 적은 수의 웜뱃을 만나야 한다.

먼저, 격자의 크기와 각 도로 세그먼트에 웜뱃이 몇 마리가 있는지가 주어진다. 

다음에는 E 개의 이벤트가 차례로 주어지는데, 각 이벤트는 아래 두 가지 중 하나의 형태이다. • change : 어떤 도로 세그먼트에 있는 웜뱃의 마릿수가 바뀐다. • escape : 사람 한 명이 수평 도로 0 번의 주어진 교차로로 도착하고, 

이 사람을 가장 적은 수의 웜뱃을 만나면서 수평 도로 R - 1 의 주어진 교차로로 보내는 경로를 구해야 한다.

위 그림은 수평도로가 R = 3 개, 수직도로가 C = 4 개, 그리고 각 도로 세그먼트에 웜뱃이 몇 마리가 있는지 주어진 지도의 처음 상황이다. 

다음 순서대로 이벤트가 발생한다고 하자.

• 한 사람이 교차로 A = (0, 2) 에 도착해서 교차로 B = (2, 1) 로 도망치고 싶어 한다. 

  이 때 만나는 웜뱃 마릿수의 최솟값은 2 인데, 점선을 따라가면 이를 확인할 수 있다. • 또 한 사람이 교차로 X = (0, 3) 에 도착해서 교차로 Y = (2, 3) 로 도망치고 싶어 한다. 

  이 때 만나는 웜뱃 마릿수의 최솟값은 7 인데, 또 점선을 따라가면 이를 확인할 수 있다. • change 이벤트가 두 번 발생한다. 수직 도로 0 의 가장 위 세그먼트에 있는 웜뱃의 수가 5 마리로 바뀌고, 

  수평 도로 1 의 가운데 세그먼트에 있는 웜뱃의 수가 6 마리로 바뀐다. 아래 그림의 동그라미를 친 숫자를 확인해보자.

• 세 번째 사람이 교차로 A = (0, 2) 에 도착해서 교차로 B = (2, 1) 로 도망치고 싶어 한다. 

  이번에는 만나게 되는 웜뱃의 최소 숫자가 5 마리이고, 다시 점선을 따라가면 이를 확인할 수 있다.