描述

新年到了，你收到了一副畫。你想找到里面最大的福字。

一副畫是一個n × n的矩陣，其中每個位置都是一個非負整數。

一個福字被定義成是大小為 k 的正方形，滿足其中的每個位置上的數都恰好比他的左邊的那個和上邊的那個大1（如果左邊或上邊的那個不存在的話就無此要求）。

比如

1 2 3 2 3 4 3 4 5

就是一個福字。（注意左上角可以是任何非負整數）。

你想找到這個矩陣中最大的福字的大小。

輸入

第一行一個數 n，表示矩陣大小。(n ≤ 1000)

接下來 n 行，每行 n 個數，表示這個矩陣。矩陣中的數在0到108之間。

輸出

一行一個數表示最大的福字的大小。

樣例輸入

樣例輸出

思路

dp[i][j]表示以第i行第j列元素為矩陣右下角所能得到的最大福字的大小。

對于這一個矩陣，dp[i][j]對于dp[i-1][j]來說屬于豎向擴充。

同理，dp[i][j]對于dp[i][j-1]來說屬于橫向擴充。

因此，在a[i-1][j]+1==a[i][j]&&a[i][j-1]+1==a[i][j]成立的前提下（擴充福字），dp[i][j]=dp[i-1][j-1]+1

其他條件便只能由所在一個元素去構成一個福字矩陣了，大小dp[i][j]=1

AC 代碼