욕심 많은 판다
시간 제한2초메모리 제한256 MB
n x n 격자에서 인접한 칸으로만 이동하며 값이 계속 증가하는 가장 긴 경로의 길이를 구합니다.
문제
n × n 크기의 대나무 숲이 있다. 욕심 많은 판다는 한 칸에서 대나무를 먹기 시작한다. 그 칸의 대나무를 모두 먹으면 위, 아래, 왼쪽, 오른쪽 중 인접한 한 칸으로 이동할 수 있다.
단, 판다는 지금 있던 칸보다 대나무가 더 많은 칸으로만 이동한다.
사육사는 판다를 어느 칸에 처음 놓고 어떤 경로로 이동시켜야 가장 많은 칸을 방문할 수 있는지 알고 싶다. 대나무 숲의 각 칸에 있는 대나무의 양이 주어질 때, 판다가 방문할 수 있는 칸 수의 최댓값을 구하라.
입력
첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다.
다음 n개의 줄에는 각 줄마다 n개의 정수가 공백으로 구분되어 주어진다. 각 정수는 해당 칸의 대나무 양이며, 대나무의 양은 1,000,000 이하의 자연수이다.
출력
판다가 방문할 수 있는 칸 수의 최댓값을 출력한다.