MENU

第七届蓝桥杯 Java B—— 方格填数

March 16, 2019 • Read: 3606 • 算法阅读设置

如下的 10 个格子

填入 0~9 的数字。要求:连续的两个数字不能相邻。
(左右、上下、对角都算相邻)

一共有多少种可能的填数方案?

  • public class Main {
  • static boolean[] book = new boolean[10];
  • static int[][] map = new int[3][4];
  • static int ans;
  • public static void main(String[] args) {
  • map[0][0] = map[2][3] = -2;
  • dfs(0, 1);
  • System.out.println(ans);
  • }
  • static void dfs(int x, int y) {
  • if (map[x][y] == -2) {
  • ans++;
  • } else {
  • for (int i = 0; i <= 9; i++) {
  • if (!book[i] && check(i, x, y)) {
  • book[i] = true;
  • map[x][y] = i;
  • dfs(x + (y + 1 == 4 ? 1 : 0), (y + 1) % 4);
  • book[i] = false;
  • }
  • }
  • }
  • }
  • static boolean check(int i, int x, int y) {
  • if (y - 1 >= 0 && Math.abs(map[x][y - 1] - i) == 1) // left
  • return false;
  • if (x - 1 >= 0 && Math.abs(map[x - 1][y] - i) == 1) // up
  • return false;
  • if (x - 1 >= 0 && y - 1 >= 0 && Math.abs(map[x - 1][y - 1] - i) == 1) // leftUp
  • return false;
  • if (x - 1 >= 0 && y + 1 < 4 && Math.abs(map[x - 1][y + 1] - i) == 1) // RightUp
  • return false;
  • return true;
  • }
  • }
Archives Tip
QR Code for this page
Tipping QR Code