2023-07-12力扣今日二题

链接：

[1895. 最大的幻方]

题意：

尺寸k的幻方，需要内部每一行每一列还有两条对角线的和相等

找最大幻方尺寸

解：

尺寸很小，50*50,

做一下行、列、对角线的前缀，然后暴力就行

由于幻方肯定存在1成立（即单个格子），所以设置ans默认为1

然后由于要找最大的，所以正在判断的尺寸k设置为从ans开始，低于ans的k没有意义

实际代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int Nmax=50;
vector<vector<int>> mp(Nmax , vector<int>(Nmax,0));
int row[Nmax][Nmax],col[Nmax][Nmax];//行前缀 列前缀
int djx1[Nmax][Nmax],djx2[Nmax][Nmax];//对角前缀 
int n,m;

int largestMagicSquare(vector<vector<int>>& grid)
{
    //int n=grid.size(),m=grid[0].size();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(j) row[i][j]=row[i][j-1]+grid[i][j];
            else row[i][j]=grid[i][j];
            
            if(i) col[i][j]=col[i-1][j]+grid[i][j];
            else col[i][j]=grid[i][j];
            
            if(i && j) djx1[i][j]=djx1[i-1][j-1]+grid[i][j];
            else djx1[i][j]=grid[i][j];
            
            if(i && j+1<m) djx2[i][j]=djx2[i-1][j+1]+grid[i][j];
            else djx2[i][j]=grid[i][j];
        }
    }
    int ans=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            for(int k=ans;i+k<n && j+k<m;k++)//实际上是正在判断的幻方尺寸是k+1
            {
                //cout<<i<<"-"<<j<<"-"<<k<<":"<<endl;
                bool success=1;//结果标识符 
                int row_k=row[i][j+k]-row[i][j]+grid[i][j];//首行和 
                int col_k=col[i+k][j]-col[i][j]+grid[i][j];//首列和
                int djx1_k=djx1[i+k][j+k]-djx1[i][j]+grid[i][j];//对角线1
                int djx2_k=djx2[i+k][j]-djx2[i][j+k]+grid[i][j+k];//对角线2
                //cout<<"[Test]:"<<row_k<<" "<<col_k<<" "<<djx1_k<<" "<<djx2_k<<endl;
                if(row_k!=col_k || row_k!=djx1_k || row_k!=djx2_k) continue;
                //cout<<"[Test]:step1 success"<<endl;
                for(int t=1;t<=k;t++)
                {
                    int row_t=i+t,col_t=j+t;
                    int row_k_t=row[row_t][j+k]-row[row_t][j]+grid[row_t][j];//行和 
                    int col_k_t=col[i+k][col_t]-col[i][col_t]+grid[i][col_t];//列和
                    //cout<<t<<"-"<<row_k_t<<"&"<<col_k_t<<endl;
                    if(row_k!=row_k_t || row_k!=col_k_t)
                    {
                        success=0;break;
                    }
                }
                
                if(success) ans=max(ans,k+1);
                
            }
        }
    }
    
    return ans;
}
int main()
{
    cin>>n>>m;
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>mp[i][j];
        }
    }
    
    int ans=largestMagicSquare(mp);
    cout<<ans<<endl;
    return 0;
}

限制：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 1 <= grid[i][j] <= 106