笔试时间：2024年10月19 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目：数独计数

时间限制: C/C++语言 1000MS;其他语言 3000MS，内存限制:C/C++语言65536KB;其他语言 589824KB

小明最近热衷于数独游戏。在厌倦了传统数独后，他想到一个有趣的规则:有3x3的方格，他要把1~9的这9个数字不重不漏地填入这9个方格，并且保证填入的每个数字周围没有临近数，例如在中间位置填了数字4，那么数字3和5不能出现在数字4上下左右四个位置中任何一个。 现在小明已经填上了几个数字，他想知道一共有多少种符合上述规则的填充方案，当且仅当至少存在一个位置在这两种方案中填充的数字不同时，两种填充方案被认为是不同的。

输入描述

第一行1个整数T，表示数据组数。

对每组数据，有三行，每行三个整数。

这三行三列中的第i行第j列的数aij代表题面描述中的3x3方格对应位置的情况。

如果aij=0表示那个格子还未填充;

如果是一个[1,9]范围内的整数表示小明已填好的数字。

保证至少有一个格子未填充，已填充的格子不会出现重复数字，但有可能不合法。

1≤T≤100，其中0≤aij≤9。

输出描述

对于每组数据，输出一行一个整数表示答案，即合法的填充方案数，使得最终结果中任何一个位置上下左右相邻的数(如果有的话)与该位置的数绝对值之差不为1，且不重不漏用完1~9这9个数字。形式化地，要求对任意位置ij满足a(i-1)j,a(¡+1)j,ai(j-1),ai(j+1)(如果存在)与aij的绝对值之差不为1，且不重不漏使用完9个数字.如果没有任何可行的方案，输出0。

样例输入

2

1 8 5

4 6 3

0 2 0

1 3 5

2 6 8

2 7 0

样例输出

2

0

参考题解

回溯枚举。由于数据只有3*3，因此直接使用暴力的解法枚举所有的可能即可。递归的参数选择从一个数组 i 开始，挨个数字去尝试，需要保证这个数字未使用过。对于每一个数字i，遍历所有可能的位置，也就是两个for枚举9宫格的可放置数字的位置。

C++：[此代码未进行大量数据的测试，仅供参考]

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

using namespace std;

int T;
vector<vector<int>> grid(3, vector<int>(3));
set<int> vst;
int res;

bool check(int x, int y, int v) {
    const int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    for (int k = 0; k < 4; k++) {
        int nx = x + directions[k][0];
        int ny = y + directions[k][1];
        if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
            if (grid[nx][ny] == 0) continue;
            if (abs(grid[nx][ny] - grid[x][y]) == 1) return false;
        }
    }
    return true;
}

void dfs(int i) {
    if (i > 9) {
        res++;
        return;
    }
    if (vst.count(i)) {
        dfs(i + 1);
        return;
    }
    for (int x = 0; x < 3; x++) {
        for (int y = 0; y < 3; y++) {
            if (grid[x][y] == 0 && check(x, y, i)) {
                grid[x][y] = i;
                dfs(i + 1);
                grid[x][y] = 0;
            }
        }
    }
}

int main() {
    cin >> T;
    while (T--) {
        vst.clear();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cin >> grid[i][j];
                if (grid[i][j] != 0) {
                    vst.insert(grid[i][j]);
                }
            }
        }

        res = 0;
        dfs(1);
        cout << res << endl;
    }
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static int[][] grid = new int[3][3];
    static Set<Integer> vst = new HashSet<>();
    static int res;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        while (T-- > 0) {
            vst.clear();
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    grid[i][j] = sc.nextInt();
                    if (grid[i][j] != 0) {
                        vst.add(grid[i][j]);
                    }
                }
            }

            res = 0;
            dfs(1);
            System.out.println(res);
        }
        sc.close();
    }

    static boolean check(int x, int y, int v) {
        int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        for (int[] dir : directions) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                if (grid[nx][ny] == 0) continue;
                if (Math.abs(grid[nx][ny] - grid[x][y]) == 1) return fals