本文主要是介绍hdu4331 Image Recognition 就暴力啊。。啊。。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给一个1和0组成的正方形矩阵，求 四条边都由1构成的正方形的个数。
方法：
先统计矩阵中每一点，向四个方向，最多有多少个连续的1，这里用dp做也
与此同时，顺便求下 能向右下和 左上 两个方向 形成的最大的正方形的边长 （就是里面的d1[][] d2[][]）
为什么朝这俩方向呢，这样方便统计最长的连续的1啊，四个方向一起好像不行啊
然后枚举边长，就没了
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;int t,T,ans,s[1005][1005],n;
int d1[1005][1005],d2[1005][1005],dt[1005][1005],dd[1005][1005],dl[1005][1005],dr[1005][1005];
//dt(top) dd(down) dl(left) dr(right)表示该点向四个方向最长有几个1
//d1表示该点向右下对角线的最长边长(即该点向下和向右短的那条边) d2表示向左上
int main()
{int i,j,k;scanf("%d",&T);t=0;while(T--){ans=0;t++;scanf("%d",&n);for(i=0;i<n;i++)for(j=0;j<n;j++){scanf("%d",&s[i][j]);if(s[i][j]) ans++;}memset(dt,0,sizeof dt);memset(dd,0,sizeof dd);memset(dr,0,sizeof dr);memset(dl,0,sizeof dl);for(i=0;i<n;i++)//右下方向{for(j=0;j<n;j++){if(s[i][j]){dd[i][j]=dd[i-1][j]+1;dr[i][j]=dr[i][j-1]+1;}d1[i][j]=min(dd[i][j],dr[i][j]);}}for(i=n-1;i>=0;i--)//左上方向{for(j=n-1;j>=0;j--){if(s[i][j]){dt[i][j]=dt[i+1][j]+1;dl[i][j]=dl[i][j+1]+1;}d2[i][j]=min(dt[i][j],dl[i][j]);}}for(i=0;i<n;i++){for(j=0;j<n;j++){for(k=2;k<=d2[i][j];k++)//枚举边长{if(k<=d1[i+k-1][j+k-1])ans++;}}}printf("Case %d: %d\n",t,ans);}return 0;
}
这篇关于hdu4331 Image Recognition 就暴力啊。。啊。。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
