개발자 크루

푼 문제 저장하기

내가 푼 문제를 저장하는 기능이 있음 좋겠어요!

푼 문제 저장하기

썸네일

함께하는 효도

난이도
3 단계
참가자
1 명
제출
1 명
정답률
100.00 %
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 2초 1024MB
Python 2초 1024MB
C++ 1초 1024MB
Java 2초 1024MB
C 1초 1024MB

남우는 m명의 친구를 불러 나무에서 열매를 수확하는 일을 맡겼습니다. 나무들은 n * n 크기의 격자 모양의 땅 위의 모든 칸에 심어져 있고, 각 나무마다 가능한 열매 수확량이 주어져 있습니다.

친구들은 n * n 크기의 격자 내의 서로 다른 위치에서 출발하여 1초에 1칸씩 상하좌우 인접한 칸 중 한 곳으로 움직일 수 있으며, 최종적으로 모든 열매 수확량의 합을 최대로 만들고자 합니다. 이때 각 칸에서 열매를 수확하는데 걸리는 시간은 0초이며, 한 나무에 여러 친구가 방문하게 되더라도 열매는 딱 한 번만 수확이 가능합니다. 이때, 친구들끼리 이동하는 도중 동시에 같은 사과나무에서 마주치는 경우에는 싸움이 일어날 수 있기 때문에 남우는 이와 같은 경우가 없기를 바랍니다.

m명의 친구들이 3초 동안 최대로 얻을 수 있는 열매 수확량의 총 합을 구하는 프로그램을 작성해보세요.


본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

  • [2024-11-27] 문제 지문 중 일부를 변경하였으며, 해당 부분에 강조/밑줄을 추가하였습니다.
    * 기존: '또, 친구들끼리 이동하는 도중 이동 경로가 겹치는 것은 불가능합니다.'
    * 변경: '이때, 친구들끼리 이동하는 도중 동시에 같은 사과나무에서 마주치는 경우에는 싸움이 일어날 수 있기 때문에 남우는 이와 같은 경우가 없기를 바랍니다.'
  • [2024-11-27] 변경된 지문과 관련하여, 테스트케이스가 추가되었으니 문제를 다시 확인해주시면 감사드리겠습니다.
제약조건

[조건 1] 2 ≤ n ≤ 20

[조건 2] 1 ≤ m ≤ 3

[조건 3] 1 ≤ 가능한 열매 수확량 ≤ 1,000

입력형식

첫 번째 줄에 n과 m이 공백을 사이에 두고 주어집니다.

두 번째 줄부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 가능한 열매 수확량 정보가 공백을 사이에 두고 주어집니다.

n + 2번째 줄부터는 m개의 줄에 걸쳐 각 친구의 위치 정보 ( Xi , Yi )가 공백을 사이에 두고 주어집니다. 이는 친구가 ( Xi 행, Yi 열)에 위치해 있음을 뜻하며, 처음 위치가 겹쳐져 주어지는 경우는 없다고 가정해도 좋습니다.

출력형식

첫 번째 줄에 얻을 수 있는 최대 열매 수확량의 합을 출력하세요. 단, 처음 시작하는 칸의 경우 0초 때 열매 수확이 가능함에 유의합니다.

입력예제1

4 2
20 26 185 80
100 20 25 80
20 20 88 99
15 32 44 50
1 2
2 3
출력예제1

633