三道模拟题

    1. 锯齿数独

    学会输入输出
    回溯 复习了解数独
    image.png
    image.png

    1. import java.util.Scanner;
    3. public class test {
    4.     static int count = 0;
    5.     public static void main(String[] args) {
    6.         Scanner scan = new Scanner(System.in);
    7.         //读取案例数
    8.         int num = scan.nextInt();
    9.         int[][] qipan = new int[3][3];
    10.         int[][] gong = new int[3][3];
    12.         for (int n = 0; n < num; ++n) {
    13.             for (int i = 0; i < 3; ++i) {
    14.                 String tmp = scan.next();
    15.                 for (int j = 0; j < tmp.length(); ++j) {
    16.                     if (tmp.charAt(j) != '*') qipan[i][j] = tmp.charAt(j) - '0';
    17.                 }
    18.             }
    20.             for (int i = 0; i < 3; ++i) {
    21.                 for (int j = 0; j < 3; ++j) {
    22.                     int x = scan.nextInt();
    23.                     int y = scan.nextInt();
    24.                     gong[x][y] = i;
    25.                 }
    26.             }
    28.             boolean res = backTrack(qipan, gong);
    29.             System.out.println(count);
    32.         }
    34.     }
    36.     private static boolean isValidSudoku(int row, int col, int val, int[][] board, int[][] gong){
    37.         // 同行是否重复
    38.         for (int i = 0; i < 3; i++){
    39.             if (board[row][i] == val){
    40.                 return false;
    41.             }
    42.         }
    43.         // 同列是否重复
    44.         for (int j = 0; j < 3; j++){
    45.             if (board[j][col] == val){
    46.                 return false;
    47.             }
    48.         }
    49.         // 宫格里是否重复
    50.         int gongHao = gong[row][col];
    51.         for (int i = 0; i < 3; ++i) {
    52.             for (int j = 0; j < 3; ++j) {
    53.                 if (gongHao == gong[i][j]) {
    54.                     if (board[i][j] == val) return false;
    55.                 }
    56.             }
    57.         }
    59.         return true;
    60.     }
    62.     public static boolean backTrack(int[][] qipan, int[][] gong) {
    63.         for (int i = 0; i < 3; ++i) {
    64.             for (int j = 0; j < 3; ++j) {
    65.                 if (qipan[i][j] != 0) continue;
    67.                 for (int k = 1; k <= 3; ++k) {
    69.                     if (isValidSudoku(i, j, k, qipan, gong)) {
    70.                         qipan[i][j] = k;
    71.                         if (backTrack(qipan, gong)) {
    72.                             //输出棋盘
    73.                             //for (int m = 0; m < 3; ++m) {
    74.                             //    for (int n = 0; n < 3; ++n) {
    75.                             //        System.out.print(qipan[m][n]);
    76.                             //    }
    77.                             //    System.out.println();
    78.                             //}
    79.                             count++;
    80.                         }
    81.                         qipan[i][j] = 0;
    82.                     }
    84.                 }
    85.                 return false;
    87.             }
    89.         }
    90.         return true;
    92.     }
    94. }
    1. 黑白棋

    used[][]数组，存放是否棋子刚刚被反转过
    used[x][y] == 0 可以反转
    反转过棋子以后 置1，used[x][y] == 1
    在下一次下棋之前（for循环的最后，将所有1置2，将所有2置0）
    image.png
    image.png

    1. 战旗