BOJ 5406 No Smoking, Please

문제 링크:

문제 내용

$r$행 $c$열의 직사각형 모양의 레스토랑이 있습니다. 이 레스토랑은 $1 \times 1$ 크기의 정사각형 방으로 나눠져 있고, 방과 방 사이에는 통로가 있을 수도 있고 없을 수도 있습니다.

이 레스토랑에서 몇 개의 통로를 막아서 두 구역으로 나누려고 합니다. 한 쪽 구역에는 출입구가, 반대쪽 구역에는 부엌이 포함되어 있어야 합니다.

어떤 통로의 면적이 $x$일 때, 이 값이 양수라면 이 통로를 막는 데 드는 비용은 $1000x + 1000$ 유로입니다. $x=0$이라면 그 벽은 이미 막혀있는 것으로, 추가 비용이 들지 않습니다.

레스토랑을 두 구역으로 나누는 데 필요한 최소 비용을 구하세요.

입력

첫 줄에는 $r$과 $c$가 주어집니다. ($1 \le r, c < 1000$)

두 번째 줄에는 출입구의 행 번호와 열 번호가 0-based로 주어지고, 세 번째 줄에는 부엌의 행 번호와 열 번호가 같은 방식으로 주어집니다.

그 다음 $r$줄에 각각 $c-1$개의 음이 아닌 정수가 주어집니다. 이는 가로 방향으로 이웃한 두 방 사이에 있는 통로의 면적입니다. 통로의 면적은 0 이상 100 미만입니다.

그 다음 $r-1$줄에 각각 $c$개의 음이 아닌 정수가 주어집니다. 이는 세로 방향으로 이웃한 두 방 사이에 있는 통로의 면적입니다.

문제 풀이