# Solution Idea

## Hint

### 10pt

• 窮舉完一列的所有數字後，檢查該列總和和目標總和是否相同，若不相同則不進行下一列的窮舉。同理類推，行的情況。
• 窮舉到一半時，檢查總和是否有超過目標總和，若發生則不進行下一個數字的窮舉。

## 參考解法

### 策略一

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <stdio.h>#include <stdlib.h>#include <string.h> int R[32], C[32], g[32][32];int n, m, n2, used[128]; int dfs(int x, int y) {    if (y == m) {        if (R[x])    return 0;        y = 0, x++;    }    if (x == n-1 && y > 0 && C[y-1])        return 0;    if (x == n) {        if (C[m-1])            return 0;        for (int i = 0; i < n; i++)            for (int j = 0; j < m; j++)                printf("%d%c", g[i][j], " \n"[j == m-1]);        return 1;    }    for (int i = 1; i <= n2; i++) {        if (used[i] || R[x] < i || C[y] < i)            continue;        R[x] -= i, C[y] -= i, g[x][y] = i;        used[i] = 1;        if (dfs(x, y+1))            return 1;        R[x] += i, C[y] += i;        used[i] = 0;    }    return 0;}int main() {    while (scanf("%d %d", &n, &m) == 2) {        int sum1 = 0, sum2 = 0;        for (int i = 0; i < n; i++)            scanf("%d", &R[i]), sum1 += R[i];        for (int i = 0; i < m; i++)            scanf("%d", &C[i]), sum2 += C[i];         memset(used, 0, sizeof(used));        n2 = n*m;        if (sum1 != n2*(n2+1)/2 || sum2 != n2*(n2+1)/2) {            printf("no solution\n");        } else {            int f = dfs(0, 0);            if (f == 0)                printf("no solution\n");        }    }    return 0;}


### 策略二

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include <stdio.h>#include <stdlib.h>#include <string.h>#include <limits.h>int R[32], C[32], g[32][32];int n, m, n2, used[128];int Rn[32], Cn[32];int min(int x, int y) {return x < y ? x : y;}int dfs(int idx) {    if (idx == n*m) {        for (int i = 0; i < n; i++) {            for (int j = 0; j < m; j++)                printf("%d%c", g[i][j], " \n"[j == m-1]);        }        return 1;    }     int x, y, mn = INT_MAX;    for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            if (g[i][j])                continue;            int t = min(R[i], C[j]);            if (t < mn)                mn = t, x = i, y = j;        }    }     for (int t = 1; t <= mn; t++) {        if (used[t])            continue;        if (Rn[x] == 1 && R[x] != t)            continue;        if (Cn[y] == 1 && C[y] != t)            continue;        R[x] -= t, C[y] -= t;        used[t] = 1, g[x][y] = t, Rn[x]--, Cn[y]--;        if (dfs(idx+1))            return 1;        R[x] += t, C[y] += t;        used[t] = 0, g[x][y] = 0, Rn[x]++, Cn[y]++;    }    return 0;}int main() {    while (scanf("%d %d", &n, &m) == 2) {        int sum1 = 0, sum2 = 0;        for (int i = 0; i < n; i++)            scanf("%d", &R[i]), sum1 += R[i], Rn[i] = m;        for (int i = 0; i < m; i++)            scanf("%d", &C[i]), sum2 += C[i], Cn[i] = n;         memset(used, 0, sizeof(used));        memset(g, 0, sizeof(g));        n2 = n*m;        if (sum1 != n2*(n2+1)/2 || sum2 != n2*(n2+1)/2) {            printf("no solution\n");        } else {            int f = dfs(0);            if (f == 0)                printf("no solution\n");        }    }    return 0;}