1792: 부스체험(large)
[만든사람 : 한진우 (2022)]
문제 설명
루루네 학교에서는 축제를 맞이하여 운동장에서 여러 개의 부스를 운영하고 있다. 부스는 N행 M열 격자판 모양으로 빈틈없이 배치되어 있으며, 모든 체험 부스는 인접한 상, 하, 좌, 우의 부스와 연결되어 있다. 올해 축제는 많은 동아리에서 참여하여 사상 최대 규모의 동아리 부스 운영이 진행되었다.
부스 체험 참가자는 (1, 1)에 위치한 부스 입구에서 입장료를 지불한 다음, 입장권을 받아야 한다.
입장료는 따로 정해져있지 않으며, 입장권에는 입장 시 참가자가 지불한 입장료의 금액이 기록된다.
예를 들어, 입장 시 입장료를 10원 지불했다면 입장권에는 10원이 기록되며, 입장권을 받은 후에는 인접한 부스로 이동하여 체험을 즐길 수 있다.
단, 인접한 부스로 이동하기 위해서는 해당 부스가 요구하는 금액 이상이 입장권에 기록되어 있어야 이동할 수 있으며, 입장권은 자유이용권 같은 개념이라 이동할 수 있는 모든 부스를 자유롭게 체험할 수 있다.
예를 들어, 운동장이 5*5 격자판 모양으로 부스가 아래 그림과 설치되었다고 가정해보자.
만약 루루가 입장료를 3원 지불했다면 영일이의 입장권에는 3이 기록되며, 입장권을 가지고 영일이는 (4, 1) 부스까지 이동하면서 경로 상의 모든 부스를 체험할 수 있다.
하지만 (2, 4) 부스와 같이 요구하는 금액이 높은 경우에는 이동하여 체험할 수 없다.
루루는 축제 전부터 (x, y)에서 운영하는 부스를 꼭 체험하고 싶었다. (x, y) 부스를 체험하기 위해 지불해야 할 입장료의 최솟값을 출력하시오.
부스 체험 참가자는 (1, 1)에 위치한 부스 입구에서 입장료를 지불한 다음, 입장권을 받아야 한다.
입장료는 따로 정해져있지 않으며, 입장권에는 입장 시 참가자가 지불한 입장료의 금액이 기록된다.
예를 들어, 입장 시 입장료를 10원 지불했다면 입장권에는 10원이 기록되며, 입장권을 받은 후에는 인접한 부스로 이동하여 체험을 즐길 수 있다.
단, 인접한 부스로 이동하기 위해서는 해당 부스가 요구하는 금액 이상이 입장권에 기록되어 있어야 이동할 수 있으며, 입장권은 자유이용권 같은 개념이라 이동할 수 있는 모든 부스를 자유롭게 체험할 수 있다.
예를 들어, 운동장이 5*5 격자판 모양으로 부스가 아래 그림과 설치되었다고 가정해보자.
만약 루루가 입장료를 3원 지불했다면 영일이의 입장권에는 3이 기록되며, 입장권을 가지고 영일이는 (4, 1) 부스까지 이동하면서 경로 상의 모든 부스를 체험할 수 있다.
하지만 (2, 4) 부스와 같이 요구하는 금액이 높은 경우에는 이동하여 체험할 수 없다.
루루는 축제 전부터 (x, y)에서 운영하는 부스를 꼭 체험하고 싶었다. (x, y) 부스를 체험하기 위해 지불해야 할 입장료의 최솟값을 출력하시오.
입력 설명
첫 번째 줄에는 운동장의 행(N)과 열(M)이 입력된다.
두 번째 줄부터 (N+1)번째 줄까지 각 부스에서 요구하는 금액(Cij)가 입력된다.
마지막 줄에는 영일이가 체험하고 싶은 부스의 위치(x, y)가 입력된다.
(1 <= N,M <= 500)
(0 < Cij <= 1,000,000, 단 C11의 값은 항상 0이 입력된다.)
(1 <= x <= N, 1 <= y <= M)
두 번째 줄부터 (N+1)번째 줄까지 각 부스에서 요구하는 금액(Cij)가 입력된다.
마지막 줄에는 영일이가 체험하고 싶은 부스의 위치(x, y)가 입력된다.
(1 <= N,M <= 500)
(0 < Cij <= 1,000,000, 단 C11의 값은 항상 0이 입력된다.)
(1 <= x <= N, 1 <= y <= M)
출력 설명
루루가 지불해야 할 입장료의 최솟값을 출력한다.
입력 예시 Copy
5 5
0 5 7 6 4
3 1 4 3 5
7 3 7 4 5
1 2 8 3 2
7 8 6 2 5
4 1
출력 예시 Copy
3