Solution Idea

50022. Matrix

Hint

90pt

排列所有數字後,放置表格檢查即可。

10pt

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

參考解法

策略一

從左上角慢慢填到右下角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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;
}

策略二

找還沒填過的最少可能方法數的格子開始填。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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;
}

策略三

先進行高斯消去法,利用 true negative P = 0 優先過濾掉無解情況。

Discussion