Solution Idea

50004. 15 - puzzle

Problem

$4 \times 4$ 的數字拼盤,總共有 15 個數字以及一個空格,目標盤面如下:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 _

給一個初始盤面以及一序列的操作步驟,只有當移動的數字在空格的上下左右位置時,此步驟才合法,否則將忽略此次移動,合法情況下將數字推入空格中。若過程中已經達到目標盤面,則中斷過程並且輸出最後一個移動的數字。

Solution

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
#include <stdio.h>
#define MAXN 4
#define swap(x, y) {int t; t = x, x = y, y = t;}
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int readboard(int g[][MAXN], int x[], int y[]) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (scanf("%d", &g[i][j]) != 1)
                return 0;
            x[g[i][j]] = i, y[g[i][j]] = j;
        }
    }
    return 1;
}
int move(int v, int g[][MAXN], int x[], int y[]) {
    if (v <= 0 || v >= MAXN*MAXN)    return 0;
    int valid = 0, end = 1;
    for (int i = 0; i < 4; i++)
        if (x[0]+dx[i] == x[v] && y[0]+dy[i] == y[v])
            valid = 1;
    if (!valid)    return 0;
    swap(g[x[0]][y[0]], g[x[v]][y[v]]);
    swap(x[0], x[v]);
    swap(y[0], y[v]);
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++)
            end &= (g[i][j] == i*MAXN+j+1 || g[i][j] == 0);
    }
    return end;
}
int main() {
    int g[MAXN][MAXN], x[MAXN*MAXN+1], y[MAXN*MAXN+1], n, v;
    while (readboard(g, x, y)) {
        int end = 0, rc = 0;
        while (scanf("%d", &v) == 1 && v) {
            if (end == 0 && move(v, g, x, y))
                end = 1, rc = v;
        }
        for (int i = 0; i < MAXN; i++)
            for (int j = 0; j < MAXN; j++)
                printf("%d%c", g[i][j], " \n"[j==MAXN-1]);
        if (end)
            printf("%d %d\n", end, rc);
        else
            printf("%d\n", end);
    }
    return 0;
}

Author

Morris

Discussion