문제 설명
특수 임무를 수행하고 있는 세종이는 N행, M열의 격자 모양의 밭에 있다.
이 밭에는 벌레가 많고, 벌레를 싫어하는 세종이는 최대한 빨리 목표 지점으로 가고 싶어한다.
세종이는 밭의 각 영역에 벌레가 몇 마리 있는지 정보를 알고 있다.
출발 지점의 좌표가 주어질 때, 벌레를 가장 적게 만나면서 목표 지점에 도달하고자 한다. 세종이는 상,하,좌,우로만 이동할 수 있다. 세종이를 도와줄 수 있는 프로그램을 작성하시오.
예를 들어, 아래와 같은 격자 모양 밭이 있고, 출발 지점과 목표 지점이 주어지면, 가장 적게 만나는 벌레의 수는 14마리이다. 각 격자 영역의 숫자는 그 영역의 벌레의 수를 뜻한다.
시작이 (3,2)이고 도착이 (2,4)일 때 화살표를 따라 이동하면 벌레를 가장 적게 만난다.
이 밭에는 벌레가 많고, 벌레를 싫어하는 세종이는 최대한 빨리 목표 지점으로 가고 싶어한다.
세종이는 밭의 각 영역에 벌레가 몇 마리 있는지 정보를 알고 있다.
출발 지점의 좌표가 주어질 때, 벌레를 가장 적게 만나면서 목표 지점에 도달하고자 한다. 세종이는 상,하,좌,우로만 이동할 수 있다. 세종이를 도와줄 수 있는 프로그램을 작성하시오.
예를 들어, 아래와 같은 격자 모양 밭이 있고, 출발 지점과 목표 지점이 주어지면, 가장 적게 만나는 벌레의 수는 14마리이다. 각 격자 영역의 숫자는 그 영역의 벌레의 수를 뜻한다.
시작이 (3,2)이고 도착이 (2,4)일 때 화살표를 따라 이동하면 벌레를 가장 적게 만난다.
입력 설명
첫째 줄에 격자 밭의 크기 \(N\)행, \(M\)열이 정수로 입력된다.\((1 \le N, M \le 200)\)
둘째 줄에 출발 지점의 행 좌표, 열 좌표, 목표 지점의 행 좌표, 열 좌표가 순서대로 입력된다.
셋째 줄부터 \(N\)행에 걸쳐 각 격자 위치\((i, j)\)의 벌레 수 \(P_{ij}\)가 순서대로 입력된다.\((1 \le P_{ij} \le 100)\)
둘째 줄에 출발 지점의 행 좌표, 열 좌표, 목표 지점의 행 좌표, 열 좌표가 순서대로 입력된다.
셋째 줄부터 \(N\)행에 걸쳐 각 격자 위치\((i, j)\)의 벌레 수 \(P_{ij}\)가 순서대로 입력된다.\((1 \le P_{ij} \le 100)\)
출력 설명
출발 지점에서 목표 지점까지 이동할 때 만나는 벌레의 최소 수를 출력한다.
입력 예시 Copy
4 4
3 2 2 4
1 3 2 1
2 20 3 2
1 2 23 3
1 1 15 2
출력 예시 Copy
14