算法1

(暴力) $O(n^2)$

时间复杂度

O(n^2)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int row[N],col[N];
int haze[N][N];
int t,n;
bool check(vector<vector<int>> g)
{
    for(int i=1;i<=n * n;i++)
    {   
        for(int j=1;j<=n * n;j++)
        {    
            row[g[i][j]]++;  
            col[g[j][i]]++;
            int cnt = n * ( (i - 1) / n )  + ( (j-1) / n ) + 1;
            haze[cnt][g[i][j]]++;
            if(row[g[i][j]] > 1 || col[g[j][j]] > 1 || haze[cnt][g[i][j]] > 1) return false;
        }
        memset(row,0,sizeof(row));
        memset(col,0,sizeof(col));
    }
    memset(haze,0,sizeof(haze));
    return true;
}
int main()
{
    cin>>t;
    for(int i=1;i<=t;i++)
    {    
        cin>>n;
        memset(row,0,sizeof(row));
        memset(col,0,sizeof(col));
        memset(haze,0,sizeof(haze));
        vector<vector<int>> g(n * n + 1,vector<int> (n * n + 1,0));
        bool legal = true;
        for(int i=1;i<=n * n;i++) 
        {   for(int j=1;j<=n * n;j++)
            {
                cin>>g[i][j];
                if(g[i][j] > n * n) legal =false;
            }
        }
        if(!legal) cout<<"Case #"<<i<<": "<<"No"<<endl;
        else 
        {
            string res = check(g)? "Yes":"No";
            cout<<"Case #"<<i<<": "<<res<<endl;
        }
    }
    return 0;
}