🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招算法题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 算法合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题，算法题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🧸 研发和算法岗的卷子第一题一样，最后一题不一样，算法岗的第二题比较困难哦

1️⃣ DFS搜索所有的状态

2️⃣ 思维难度较大，预处理+二分+单调队列

♟️ 01.LYA的魔法棋盘 评测链接🔗

问题描述

LYA是一位年轻的魔法师，她最近发明了一种奇特的魔法棋盘游戏。这个棋盘是一个 的方格，需要将数字 到 不重不漏地填入其中。但是，这个棋盘有一个特殊的魔法规则：任何相邻的数字（上下左右）之间的差的绝对值不能为 。

例如，如果在中间位置填了数字 ，那么数字 和 就不能出现在数字 的上下左右四个位置中的任何一个。

LYA已经在棋盘上填了一些数字，她想知道还有多少种不同的方法可以完成这个魔法棋盘。当且仅当至少有一个位置在两种填法中填充的数字不同时，这两种填法才被认为是不同的。

输入格式

第一行包含一个整数 ，表示测试用例的数量。

对于每个测试用例，有三行输入，每行包含三个整数。这 的数字矩阵代表 LYA 的魔法棋盘当前状态。如果某个位置的数字为 ，表示该位置尚未填充；如果是 到 之间的整数，则表示 LYA 已经在该位置填入的数字。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示完成魔法棋盘的合法方案数。如果没有任何可行的方案，输出 。

样例

样例输入1

2
1 8 5
4 6 3
0 2 0
1 3 5
2 6 8
2 7 0

样例输出1

2
0

样例解释

数据范围

• 
• ，其中 表示输入矩阵中第 行第 列的数字

题解

DFS

需要一个函数来检查当前填入的数字是否合法。这个函数需要检查：

• 填入的数字是否与周围（上下左右）的数字相差1
• 填入的数字是否已经在棋盘上出现过

DFS 来尝试填充每个空位：

• 如果当前位置已经有数字，就移动到下一个位置
• 如果当前位置是空的，尝试填入1到9的每个数字
• 对于每次尝试，都检查是否合法
• 如果合法，继续填充下一个位置
• 如果所有位置都填满了，就找到了一个合法方案，计数加1

1. 在搜索过程中，使用一个布尔数组来记录哪些数字已经被使用，这样可以快速检查是否有重复数字。

2. 时间复杂度分析：最坏情况下，我们需要尝试9!种排列，即O(9!)。但实际上，由于题目的限制条件，大多数情况下搜索树会被很快剪枝，实际运行时间会比理论上的最坏情况好得多。

3. 空间复杂度：只需要O(1)的额外空间来存储棋盘和已使用数字的标记。

参考代码

• Python

# 读取测试用例数量
T = int(input())

# 定义方向数组，用于检查相邻位置
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def is_valid(board, x, y, num):
    """
    检查在位置(x, y)放置数字num是否合法
    """
    # 检查相邻位置
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if 0 <= nx < 3 and 0 <= ny < 3:
            if board[nx][ny] != 0 and abs(board[nx][ny] - num) == 1:
                return False
    return True

def dfs(board, x, y, used):
    """
    深度优先搜索填充棋盘
    """
    # 如果已经填充完所有位置，找到一个解
    if x == 3:
        return 1
    
    # 移动到下一个位置
    next_x, next_y = (x, y + 1) if y < 2 else (x + 1, 0)
    
    # 如果当前位置已经有数字，直接处理下一个位置
    if board[x][y] != 0:
        return dfs(board, next_x, next_y, used)
    
    count = 0
    # 尝试填充1-9的数字
    for num in range(1, 10):
        if not used[num] and is_valid(board, x, y, num):
            board[x][y] = num
            used[num] = True
            count += dfs(board, next_x, next_y, used)
            board[x][y] = 0
            used[num] = False
    
    return count

# 处理每个测试用例
for _ in range(T):
    board = [list(map(int, input().split())) for _ in range(3)]
    used = [False] * 10
    
    # 标记已使用的数字
    for row in board:
        for num in row:
            if num != 0:
                used[num] = True
    
    # 计算合法方案数
    result = dfs(board, 0, 0, used)
    print(result)

• Java

import java.util.*;

public class Main {
    // 定义方向数组，用于检查相邻位置
    static int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        
        for (int t = 0; t < T; t++) {
            int[][] board = new int[3][3];
            boolean[] used = new boolean[10];
            
            // 读取棋盘状态
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    board[i][j] = scanner.nextInt();
                    if (board[i][j] != 0) {
                        used[board[i][j]] = true;
                    }
                }
            }
            
            // 计算并输出结果
            System.out.println(dfs(board, 0, 0, used));
        }
    }
    
    // 检查在位置(x, y)放置数字num是否合法
    static boolean isValid(int[][] board, int x, int y, int num) {
        for (int[] dir : directions) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                if (board[nx][ny] != 0 && Math.abs(board[nx][ny] - num) == 1) {
                    return false;
                }
            }
        }
        return true;
    }
    
    // 深度优先搜索填充棋盘
    static int dfs(int[][] board, int x, int y, boolean[] used) {
        if (x == 3) {
            return 1;
        }
        
        int nextX = y == 2 ? x + 1 : x;
        int nextY = y == 2 ? 0 : y + 1;
        
        if (board[x][y] != 0) {
            return dfs(board, nextX, nextY, used);
        }
        
        int count = 0;
        for (int num = 1; num <= 9; num++) {
            if (!used[num] && isValid(board, x, y, num)) {
                board[x][y] = num;
                used[num] = true;
                count += dfs(board, nextX, nextY, used);
                board[x][y] = 0;
                used[num] = false;
            }
        }
        
        return count;
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 定义方向数组，用于检查相邻位置
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

// 检查在位置(x, y)放置数字num是否合法
bool is_valid(vector<vector<int>>& board, int x, int y, int num) {
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
            if (board[nx][ny] != 0 && abs(board[nx][ny] - num) == 1) {
                return false;
            }
        }
    }
    return true;
}

// 深度优先搜索填充棋盘
int dfs(vector<vector<int>>& board, int x, int y, vector<bool>& used) {
    if (x == 3) {
        return 1;
    }
    
    int next_x = y == 2 ? x + 1 : x;
    int next_y = y == 2 ? 0 : y + 1;
    
    if (board[x][y] != 0) {
        return dfs(board, next_x, next_y, used);
    }
    
    int count = 0;
    for (int num = 1; num <= 9; ++num) {
        if (!used[n