dlaud5379   1년 전

(DeepL로 영어로 번역한 텍스트를 중역했습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

백준랜드 워터파크의 새로운 관리자가 된 잇창명은 현재 워터파크에서 근무하는 직원들을 조사하고 있다. 특히 잇창명은 안전요원들 중 누가 열심히 일하고, 누가 설렁설렁 일하는지 알고 싶어한다. 성실한 안전요원은 아이들이 많은 곳에서 근무하고 게으른 안전요원은 아이들이 적은 곳을 선호하므로, 안전요원의 근면도를 그 안전요원이 감시하는 아이들의 수로 정의하자.

워터파크는 한 변의 길이가 n인 정사각형이며, 한 변의 길이가 1인 n2개의 정사각형 구역으로 나누어져 있다. 각 구역은 수영장이거나 수영장을 잇는 복도이며, 각 수영장에서는 정해진 수의 아이들이 놀고 있다.

워터파크에는 안전요원 근무지가 r곳 있다. 워터파크의 안전수칙에 의해 모든 안전요원은 복도 위를 걷거나 수영장 안에서 이동하는 경우를 모두 포함해서 워터파크의 외벽에 평행으로만 이동할 수 있다. 즉, 안전요원이 한 점 (x1, y1)에서 다른 점 (x2, y2)로 이동할 때의 거리는 |x1 - x2| + |y1 - y2|가 된다. 각각의 안전요원마다 감시해야 하는 구역이 있으며, i번 안전요원의 감시 구역은 i번째 근무지에서 거리가 li 이하인 모든 수영장으로 정해져 있다.

각 안전요원의 근면도를 구하는 프로그램을 작성하여라.

입력

첫째 줄에 워터파크의 한 변의 길이 n과 안전요원의 수 r이 공백으로 구분되어 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ r ≤ n2)

다음 n줄에 걸쳐 워터파크의 지도가 주어진다. 이 중 i번째 줄은 워터파크의 i번째 줄의 정보에 해당하며, n개의 음이 아닌 정수 ai,1, ai,2, ..., ai,n이 공백으로 구분되어 주어진다. (0 ≤ ai,j ≤ 106) ai,j가 0인 경우는 (i, j)에 해당하는 구역이 복도이고, ai,j가 양수인 경우는 (i, j)에 해당하는 구역이 수영장이며 ai,j명의 아이들이 있는 것이다.

다음 r줄에 걸쳐 안전요원의 정보가 주어진다. 이 중 i번째 줄에는 세 정수 xi, yi, li가 공백으로 구분되어 주어지며, i번째 안전요원의 근무지가 (xi, yi)이고 최대 li만큼 떨어진 수영장까지를 감시한다는 의미이다.

테스트 케이스 중 50%에서는 서로 다른 둘 이상의 안전요원이 같은 수영장을 감시하는 경우는 없다고 가정해도 된다.

출력

r줄에 걸쳐 각 안전요원의 근면도를 출력한다. 이 중 i번째 줄에는 i번째 안전요원의 근면도 pi를 출력한다.

댓글을 작성하려면 로그인해야 합니다.