50016. 15-Puzzle
難度：4.5/5
Second Try: 4.5/5 Used Time: 43:23
第一次寫爛了，第二次寫了10分鐘就過。注意recursion的時候不要過度依global variable，值有可能被覆蓋掉。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#include <stdio.h>
#include <stdlib.h>
int k;
int board[4][4];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int solved = 0;
int is_valid(int x, int y){
if(x < 4 && x >= 0 && y < 4 && y >= 0) return 1;
return 0;
}
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void get_info(int* cnt, int* z_x, int* z_y){
*cnt = 0;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
if(board[i][j] == i * 4 + j + 1) (*cnt)++;
if(board[i][j] == 0) (*z_x) = i, (*z_y) = j;
}
}
}
void solve(int d){
int cnt, z_x, z_y; get_info(&cnt, &z_x, &z_y);
if(cnt == 15){
solved = 1; return;
}
if(d + (15 - cnt) > k){
return;
}
if(d == k) return;
for(int i = 0; i < 4; i++){
int neigh_x = z_x + dx[i], neigh_y = z_y + dy[i];
if(is_valid(neigh_x, neigh_y)){
swap(&board[z_x][z_y], &board[neigh_x][neigh_y]);
solve(d + 1);
swap(&board[z_x][z_y], &board[neigh_x][neigh_y]);
}
}
}
int main(){
while(scanf("%d", &k) == 1){
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
scanf("%d", &board[i][j]);
}
}
solved = 0;
solve(0);
printf("%d\n", solved);
}
return 0;
}
I originally calculated cnt_w like:1
2
3
4int now_w = cnt_w;
if(arr[x][y] == x * 4 + y + 1) now_w--;
int rtv = dfs(arr, now_x, now_y, now_w, k - 1);
Take 2: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#include <stdio.h>
#include <string.h>
void swap(int* x, int* y){
int t = *x;
*x = *y;
*y = t;
}
int arr[4][4];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int count_wrong(int arr[4][4]){
int cnt = 0;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
if(i == 3 && j == 3) break;
if(arr[i][j] != i * 4 + j + 1) cnt++;
}
}
// printf(">%d<\n", cnt);
return cnt;
}
static inline int is_valid(int x, int y){
return x >= 0 && y >= 0 && x < 4 && y < 4;
}
void print_arr(int arr[4][4]){
for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) printf("%d%c", arr[i][j], j == 3 ? '\n' : ' ');
}
int dfs(int arr[4][4], int x, int y, int cnt_w, int k){
// int cnt_w = count_wrong(arr);
if(cnt_w == 0) return 1;
if(k == 0) return 0;
if(cnt_w > k) return 0;
for(int i = 0; i < 4; i++){
int now_x = x + dx[i], now_y = y + dy[i];
if(!is_valid(now_x, now_y)) continue;
swap(&arr[x][y], &arr[now_x][now_y]);
int now_w = cnt_w;
if(arr[x][y] == x * 4 + y + 1) now_w--;
int rtv = dfs(arr, now_x, now_y, now_w, k - 1);
if(rtv) return 1;
swap(&arr[x][y], &arr[now_x][now_y]);
}
}
int main(){
int k;
while(scanf("%d", &k) != EOF){
for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) scanf("%d", &arr[i][j]);
// for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) printf("%d%c", arr[i][j], j == 3 ? '\n' : ' ');
int x, y;
for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++){
if(arr[i][j] == 0){
x = i, y = j;
break;
}
}
int rtv = dfs(arr, x, y, count_wrong(arr), k);
printf("%d\n", rtv);
}
}