문제
한 꽃밭에 메뚜기가 살고 있다. 꽃밭은 N행 N열의 정사각형들로 이뤄져 있으며, 각 칸에는 꽃이 하나씩 위치해 있다.
당신은 꽃밭 내의 각 꽃들에 대해 몇 개의 꽃잎을 가지고 있는지를 알고 있다.
메뚜기는 처음 R행 C열의 위치의 꽃에 앉아 있다. 메뚜기는 최대한 많은 꽃들을 방문하고자 한다.
메뚜기는 반드시 다음의 규칙을 지켜야 한다.
1. 메뚜기는 인접한 행 혹은 열로 이동이 가능하다. 인접한 행으로 메뚜기가 점프를 했을 경우 적어도 두 칸 이상 떨어진 열로 이동하여야 하며,
인접한 열로 이동하였을 경우에는 적어도 두 칸 이상 떨어진 행으로 이동해야 한다.
다시 말해서 (r1 c1)에서 (r2 c2)로 이동할 경우 다음의 조건을 만족해야 한다.
|r1-r2|=1 이고 |c1-c2|>1 혹은 |c1-c2|=1 이고 |r1-r2|>1
2. 이동하게 되는 다음 꽃의 꽃잎의 수는 현재 꽃의 꽃잎 수 보다 커야 한다.
메뚜기가 방문하게 되는 최대 꽃의 수를 알아내는 프로그램을 작성하라.
입력
입력의 첫 번째 줄에는 N(1≤N≤1,500)이 입력된다.
입력의 두 번째 줄에는 R(1≤R≤N)과 C(1≤C≤N)이 입력되며, 메뚜기의 처음 위치의 행과 열을 뜻한다.
마지막으로 N행 N열의 꽃밭의 정보가 입력되는데, 각 칸은 해당 위치의 꽃들의 꽃잎의 수를 뜻한다.
50%의 데이터는 N이 100 이하로 입력된다.
80%의 데이터는 N이 1,000 이하로 입력된다.
꽃잎의 수는 1,000,000보다 작거나 같다.
출력
메뚜기가 방문하게 되는 최대 꽃 수를 출력한다.
예제1
4
11
1234
2345
3456
4567
4
예제2
5
33
2016251712
1113133017
1529102611
2719142422
2321281813
21