Untitled

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);
        }
        Queue<Integer> q = new LinkedList<>();
        int startState = encode(board);
        q.add(startState);
        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;
                        q.add(nextState);
                    }
                    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;
    }
}
```