【团体程序设计天梯赛】L2-052 吉利矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了【团体程序设计天梯赛】L2-052 吉利矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【团体程序设计天梯赛】L2-052 吉利矩阵,算法,c++

思路：

直接回溯枚举每一个位置填的数，二维肯定是不方便的，我们转成一维，下标x从0到n*n-1。二维数组下标从0到n-1，在一维中下标为x的点在二维中对应行是x/n，列是x%n。

每个数最小能填的是0，最大肯定就是l了，时间复杂度的上限是n的2l次幂，4的18大概是1e11这样。

我们直接标记每行sum和每列sum，因为只有当前填的元素只会影响它所在的行和列，所以只要判断它所在行和列是否满足条件就行了。剪枝一下，具体的就是，当前和不能大于l，因为后面还有元素要加，以及，当前和加上后面元素的最大和能够大于等于l。文章来源地址https://www.toymoban.com/news/detail-859589.html

代码：

#include <iostream>
using namespace std;
int l,n,row[5],col[5],ans;

void backtrack(int x){
    if(x==n*n){
        for(int i=0;i<n;i++){
            if(row[i]!=l) return;
            if(col[i]!=l) return;
        }
        ans++;
        return;
    }
    for(int i=0;i<=l;i++){//能填的数最小是0，最大是l
        //剪枝1：当前行或列值不超过l
        if(row[x/n]+i>l||col[x%n]+i>l) break;
        row[x/n]+=i;//对应行和更新
        col[x%n]+=i;//对应列和更新
        //剪枝2：加上其他没有填的数（取最大）能达到l
        if(row[x/n]+l*(n-1-x%n)>=l&&col[x%n]+l*(n-1-x/n)>=l)
            backtrack(x+1);
        row[x/n]-=i;//还原现场
        col[x%n]-=i;
    }
}
int main(){
    cin>>l>>n;
    backtrack(0);
    cout<<ans;
    return 0;
}

到了这里，关于【团体程序设计天梯赛】L2-052 吉利矩阵的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！