天梯赛随笔

吉祥矩阵

思路：爆搜+剪枝，每一行、每一列搜索至末尾时直接判断该填的数字，可行则继续搜索。对于其他位置只搜索范围内的数字

代码：

//吉祥矩阵
#include<bits/stdc++.h>
using namespace std;

int n, m, ans;
int row[5], col[5];
int a[5][5];

bool check() {
    for (int i = 0; i < n; i ++) {
        if (row[i] != m || col[i] != m) return false;
    }
    return true;
}

void dfs(int idx) {
    if (idx == n*n) {
        if (check()) ans ++;
        return;
    }
    int r = idx / n, c = idx % n;
    if (c == n-1) {
        int temp = m - row[r];
        if (m - col[c] >= temp) {
            a[r][c] = temp;
            col[c] += temp; row[r] += temp;
            dfs(idx+1);
            col[c] -= temp; row[r] -= temp;
        }
    }
    else if (r == n-1) {
        int temp = m - col[c];
        if (m - row[r] >= temp) {
            a[r][c] = temp;
            col[c] += temp; row[r] += temp;
            dfs(idx+1);
            col[c] -= temp; row[r] -= temp;
        }
    }
    else {
        for (int i = 0; i <= min(m-row[r], m-col[c]); i ++) {
            a[r][c] = i;
            row[r] += i; col[c] += i;
            dfs(idx+1);
            row[r] -= i; col[c] -= i;
        }
    }
}

int main() {
    cin >> m >> n;
    dfs(0);
    cout << ans << endl;
}