题目：http://acm.hdu.edu.cn/showproblem.php?pid=1838
这题也挺不错的。首先题目说了，棋盘的右下角一定是‘1‘,另外棋盘里面至少包含一个1，所以最小值是1，然后初始化，刚开始想错了，以为只tu[1][j]==‘1‘||tu[j][1]==‘1‘时，
dp[1][i]与dp[i][1]才初始化为1，这样是错误的，具体请看代码红色部分，不解释了，直接意会不可言传啊。之后再补一遍吧。
转移方程：
if(tu[i][j]!=tu[i-1][j]&&tu[i][j]!=tu[i][j-1]&&tu[i][j]==tu[i-1][j-1])
dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
else dp[i][j]=1;
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> #define inf 0x3f3f3f3f typedef __int64 ll; using namespace std; int n,dp[2010][2010]; char tu[2010][2010]; int main() { int T,cnt,maxx; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%s",tu[i]+1); } memset(dp,0,sizeof(dp)); for(int i=1; i<=n; i++) { dp[1][i]=1; dp[i][1]=1; } maxx=1; for(int i=2; i<=n; i++) { for(int j=2; j<=n; j++) { if(tu[i][j]!=tu[i-1][j]&&tu[i][j]!=tu[i][j-1]&&tu[i][j]==tu[i-1][j-1]) dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1; else dp[i][j]=1; if(tu[i][j]==‘1‘) { maxx=max(maxx,dp[i][j]); } } } cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) if(dp[i][j]==maxx&&tu[i][j]==‘1‘) cnt++; } printf("%d %d\n",maxx,cnt); } return 0; }
原文：http://www.cnblogs.com/zhangmingcheng/p/4381586.html