题解 P1387 【最大正方形】

#一道关于搜索的题 这道题可以用搜索来做，判断如果是一个·正方形就往下延伸，再让ans++，在选取最大的ans即可。我第一次提交90分，就是因为多了一句话（已经注释掉），不需要判断x+1，y+1这个点，这是多余的！ ```cpp #include<bits/stdc++.h> using namespace std; bool a[105][105]={0}; int n,m,ans,xx,yy,maxn; int dfs(int x,int y){ // if(!a[x+1][y+1])//多余 // return 0; for(int i=xx;i<=x;i++)//检测正方形的左边 if(!a[i][y]) return 0; for(int j=yy;j<=y;j++)//检测正方形的下面 if(!a[x][j]) return 0; ans++;//让ans++并更新新的正方形 dfs(x+1,y+1); return ans;//若反回此处则返回ans } int main(){ //freopen("1387.in ","r",stdin); //freopen("1387.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)//离线输入 cin>>a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)//枚举每个点 if(a[i][j]){//枚举左上角的点 xx=i;//记录起始点的位置 yy=j; ans=0;//清空ans maxn=max(maxn,dfs(i,j));//求出dfs（i，j)的最大值 } cout<<maxn; return 0; } ```