메뚜기

시간 제한4초메모리 제한128 MB

요약
N×N 격자에서 특수한 이동 규칙과 꽃잎 수가 엄격히 증가해야 하는 조건 아래 시작 칸에서 방문 가능한 최대 꽃 개수를 구합니다.
난이도

어려움10점 중 8점

유형
동적 계획법, 행렬, 정렬
정답자
아직 제출이 없습니다

문제

N행 N열의 꽃밭에 각 칸마다 꽃이 하나씩 심어져 있다. 메뚜기는 처음에 R행 C열의 꽃 위에 있으며, 모든 꽃의 꽃잎 수를 알고 있다.

메뚜기는 다음 규칙을 지키며 최대한 많은 꽃을 방문하려고 한다.

  1. 메뚜기는 인접한 행 또는 인접한 열에 있는 꽃으로 점프할 수 있다. 인접한 행으로 이동할 때는 열을 적어도 2칸 이상 건너뛰어야 하고, 인접한 열로 이동할 때는 행을 적어도 2칸 이상 건너뛰어야 한다. 즉, (r1, c1)에서 (r2, c2)로 점프할 수 있으려면 다음 중 하나를 만족해야 한다.

    • |r1-r2| = 1이고 |c1-c2| > 1
    • |c1-c2| = 1이고 |r1-r2| > 1

  2. 점프하려는 꽃의 꽃잎 수는 현재 꽃의 꽃잎 수보다 많아야 한다.

시작한 꽃을 포함해 메뚜기가 방문할 수 있는 꽃의 최대 개수를 구하라.

입력

첫째 줄에 N이 주어진다. (1 <= N <= 1500)

둘째 줄에 메뚜기의 시작 위치 R과 C가 주어진다. (1 <= R, C <= N)

다음 N개 줄에는 각 꽃의 꽃잎 수가 N개씩 주어진다. 꽃잎 수는 1,000,000 이하이다.

출력

메뚜기가 방문할 수 있는 꽃의 최대 개수를 출력한다.

예제2

  1. 예제 1

    입력
    4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
    예상 출력
    4

  2. 예제 2

    입력
    5
3 3
20 16 25 17 12
11 13 13 30 17
15 29 10 26 11
27 19 14 24 22
23 21 28 18 13
    예상 출력
    21