# Untitled

unknown
plain_text
a year ago
2.8 kB
1
Indexable
Never
```Dưới đây là một giải pháp cho bài toán Turn Over Game sử dụng Java và thuật toán BFS:

```java
import java.util.*;

public class TurnOverGame {
static final int N = 4;
static final int[] dx = {0, 0, -1, 1};
static final int[] dy = {-1, 1, 0, 0};
static int[][] board = new int[N][N];
static int[][] dist = new int[1 << N * N][1 << N * N];

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 1; t <= T; t++) {
for (int i = 0; i < N; i++) {
String row = sc.next();
for (int j = 0; j < N; j++) {
board[i][j] = row.charAt(j) == 'w' ? 0 : 1;
}
}
System.out.println("Case #" + t);
System.out.println(solve());
}
}

public static String solve() {
for (int i = 0; i < (1 << N * N); i++) {
Arrays.fill(dist[i], -1);
}
int startState = encode(board);
dist[startState][startState] = 0;
while (!q.isEmpty()) {
int state = q.poll();
decode(state, board);
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
flip(x, y);
int nextState = encode(board);
if (dist[startState][nextState] == -1) {
dist[startState][nextState] = dist[startState][state] + 1;
}
flip(x, y);
}
}
}
if (dist[startState][0] != -1) return String.valueOf(dist[startState][0]);
if (dist[startState][(1 << N * N) - 1] != -1) return String.valueOf(dist[startState][(1 << N * N) - 1]);
return "impossible";
}

public static void flip(int x, int y) {
board[x][y] ^= 1;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
board[nx][ny] ^= 1;
}
}
}

public static void decode(int state, int[][] board) {
for (int i = N - 1; i >= 0; i--) {
for (int j = N - 1; j >= 0; j--) {
board[i][j] = state & 1;
state >>= 1;
}
}
}

public static int encode(int[][] board) {
int state = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
state <<= 1;
state |= board[i][j];
}
}
return state;
}
}
``````