-
Notifications
You must be signed in to change notification settings - Fork 0
/
Q39.java
99 lines (81 loc) · 2.4 KB
/
Q39.java
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class Q39 {
static final int SIZE = 4;
static final int SQ_SIZE = SIZE * SIZE;
public static void main (String[] args) {
int ans = 0;
Set<Integer> set_status_board_alreay_searched = new HashSet<>();
Queue<Integer> q_status_board = new LinkedList<>();
Queue<Integer> q_cnt = new LinkedList<>();
q_status_board.add(0);
q_cnt.add(0);
while (!q_cnt.isEmpty()) {
int status_board = q_status_board.poll();
int cnt = q_cnt.poll();
ans = Math.max(ans, cnt);
for (int y = 0; y < SIZE; y++) {
for (int x = 0; x < SIZE; x++) {
boolean[][] board = int_to_board(status_board);
boolean[][] rev_board = reverse(board, y, x);
int status_board_rev = board_to_int(rev_board);
if (set_status_board_alreay_searched.contains(status_board_rev)) continue;
set_status_board_alreay_searched.add(status_board_rev);
q_status_board.add(status_board_rev);
q_cnt.add(cnt + 1);
}
}
}
System.out.println(ans);
}
public static boolean[][] int_to_board (int n) {
boolean[][] ret = new boolean[SIZE][SIZE];
String str = Integer.toBinaryString(n);
while (str.length() < SQ_SIZE) str = "0" + str;
char[] c = str.toCharArray();
int ci = 0;
for (int j = 0; j < SIZE; j++) {
for (int k = 0; k < SIZE; k++) {
ret[j][k] = c[ci++] == '1';
}
}
return ret;
}
public static int board_to_int (boolean[][] board) {
String str = "";
for (int i = 0; i < SQ_SIZE; i++) {
str += board[i / SIZE][i % SIZE] ? "1" : "0";
}
return Integer.parseInt(str, 2);
}
public static boolean[][] reverse (boolean[][] board, int y, int x) {
boolean[][] ret = copy(board);
// 反転
for (int i = 0; i < SIZE; i++) {
ret[y][i] = !ret[y][i];
ret[i][x] = !ret[i][x];
}
ret[y][x] = !ret[y][x];
return ret;
}
public static boolean[][] copy (boolean[][] ary) {
boolean[][] ret = new boolean[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
ret[i][j] = ary[i][j];
}
}
return ret;
}
public static void debug (boolean[][] board) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
System.out.print(board[i][j] ? "■" : "□");
}
System.out.println();
}
System.out.println();
}
}