解題區/解題區 - POJ

POJ 1166 - The Clocks

contents

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Description

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|-------|    |-------|    |-------|
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
|-------|    |-------|    |-------|
    A            B            C    
|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F    
|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

(Figure 1)

There are nine clocks in a 3*3 array (figure 1). The goal is to return all the dials to 12 o’clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number 1 to 9. That number will turn the dials 90’ (degrees) clockwise on those clocks which are affected according to figure 2 below.

Move Affected clocks
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI

(Figure 2)

Input

Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o’clock, 1=3 o’clock, 2=6 o’clock, 3=9 o’clock.

Output

Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o’clock. You are convinced that the answer is unique.

Sample Input

1
2
3
3 3 0
2 2 2
2 1 2

Sample Output

1
4 5 8 9

Solution

原來之前寫過這一題，請參閱 d730: 升旗典礼 ——加强版

用 BFS 從 0 0 0 0 0 0 0 0 0 開始倒推回去，在 mark 的部份，用 4 進制 bitmask。

這題在 POJ 似乎只有一組測資，在 Zerojudge 則有非常多筆測資。

而事實上網路上還有另外一個高斯消去法，先預求反矩陣，之後直接帶入計算即可。沒有仔細去研究，不過聽說那解法限定一定有合法解，如何判定不合法解又是另外一個問題。總之，用了 BFS 過了就沒仔細去探討其他解法。

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
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <queue>
using namespace std;
char mark[1<<18] = {}, ans[1<<18], best[1<<18];
char dirp[4] = {-3, 1, 1, 1};
int next[1<<18] = {};
int pow4[10] = {1};
int move[10][7] = { {},
                 	{1, 2, 4, 5, 0},
                 	{1, 2, 3, 0},
                 	{2, 3, 5, 6, 0},
                 	{1, 4, 7, 0},
                 	{2, 4, 5, 6, 8, 0},
                 	{3, 6, 9, 0},
                 	{4, 5, 7, 8, 0},
                 	{7, 8, 9, 0},
                 	{5, 6, 8, 9, 0}
                   };
void trans(int N, char s[]) {
    int i = 0;
    while(N) {
        s[i++] = N%4, N /= 4;
    }
}
void build() {
    int a, b, c, qt = 0, t, p;
    queue<int> Q;
    best[0] = 0, mark[0] = 1;
    Q.push(0);
    while(!Q.empty()) {
    	int state = Q.front();
    	Q.pop();
    	char buf[10] = {};
    	trans(state, buf);
    	for(int i = 1; i < 10; i++) {
    		int nstate = state;
    		for(int j = 0; move[i][j]; j++)
    			nstate -= pow4[move[i][j] - 1] * dirp[buf[move[i][j] - 1]];
    		if(mark[nstate] == 0) {
    			mark[nstate] = 1;
    			next[nstate] = state;
                best[nstate] = best[state] + 1;
                ans[nstate] = i + '0';
    			Q.push(nstate);
    		}
    	}
    }
}
int print_f = 0;
void Print(int state) {
    if(state) {
        Print(next[state]);
        if(print_f)
            putchar(' ');
        print_f = 1;
        putchar(ans[state]);
    }
}
int main() {
    for(int i = 1; i < 10; i++)
        pow4[i] = pow4[i-1] * 4;
    build();
    while(true) {
    	int state = 0, x;
        for(int i = 0; i < 9; i++) {
            if(scanf("%d", &x) != 1)
            	return 0;
            state |= x * pow4[i];
        }
        print_f = 0;
        Print(state);
        puts("");
    }
    return 0;
}