C语言实现-蓝桥杯官网运行100%通过

解题思路:

题目要求在满足数字循环序列、访问所有格子且路径不交叉的条件下，找到字典序最小的路径。解决该问题的关键在于高效搜索与严格条件验证，具体思路如下：

1、预处理数字检查
        统计每个数字的总出现次数，验证其是否符合理论分布。例如，总共有 N² 个格子，每个数字 d必须恰好出现 ⌊N²/K⌋或 ⌊N²/K⌋+1 次。若不符合，直接返回无解。

2、深度优先搜索（DFS）与剪枝

    方向尝试顺序：按方向编号 0~7 顺序尝试移动，确保找到的第一个解即为字典序最小。

    数字匹配：下一步的格子数字必须为当前期望值 (u+1)%K，否则跳过。

    交叉检测：通过记录斜向移动的中点坐标（如从 (x,y)移动到 (x+1,y+1) 时，中点 (2x+1,2y+1)被标记），防止路径交叉。

    剩余数字检查：动态维护剩余各数字的数量，若后续步数无法满足序列需求，提前剪枝。

3、路径终止条件
当路径长度达到 N²−1 且位于终点 (N−1,N−1)时，记录路径并终止搜索。

注意事项：

在该平台代码会有一个通过不了，但在蓝桥杯官网可以全部通过。

参考代码:

#include <stdio.h>

#include <string.h>

#define N 20

#define K_MAX 11

int n, k;

int a[N][N];

int vis[N][N];

int mid_visited[2*N][2*N]; // 记录斜向移动的中点，防止交叉

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int path[N * N];

int path_len = 0;

char ans[N * N + 1];

int found = 0;

int total[K_MAX]; // 每个数字的总出现次数

int left[K_MAX];  // 剩余未访问的数字次数

// 预处理检查数字次数是否符合要求

int precheck() {

    int L = n * n;

    int times = L / k;

    int rem = L % k;

    for (int d = 0; d < k; d++) {

        int required = (d < rem) ? (times + 1) : times;

        if (total[d] != required) {

            return 0;

        }

    }

    // 检查终点数字是否匹配

    int final_step = n * n - 1;

    int expected_final = final_step % k;

    if (a[n-1][n-1] != expected_final) {

        return 0;

    }

    return 1;

}

int check(int x, int y, int dir) {

    if (x < 0 || x >= n || y < 0 || y >= n) return 0;

    if (vis[x][y]) return 0;

    // 斜向移动时检查中点是否被占用

    if (dir % 2 != 0) {

        int prev_x = x - dx[dir];

        int prev_y = y - dy[dir];

        int mx = 2 * prev_x + dx[dir];

        int my = 2 * prev_y + dy[dir];

        if (mx >= 0 && mx < 2*N && my >= 0 && my < 2*N && mid_visited[mx][my]) {

            return 0;

        }

    }

    return 1;

}

void dfs(int x, int y, int u) {

    if (a[x][y] != u) return;

    // 剩余步数检查

    int t_plus_1 = n * n - path_len - 1;

    if (t_plus_1 < 0) return;

    // 计算剩余序列的数字需求

    int start_r = (u + 1) % k;

    int m = t_plus_1;

    int cycle = m / k;

    int r = m % k;

    for (int d = 0; d < k; d++) {

        int expected = cycle;

        if (((d - start_r + k) % k) < r) expected++;

        if (expected > left[d]) return;

    }

    if (path_len == n * n - 1 && x == n - 1 && y == n - 1) {

        for (int i = 0; i < path_len; i++) ans[i] = path[i] + '0';

        ans[path_len] = '\0';

        found = 1;

        return;

    }

    for (int i = 0; i < 8; i++) {

        int tx = x + dx[i], ty = y + dy[i];

        if (check(tx, ty, i)) {

            int next_val = (u + 1) % k;

            if (a[tx][ty] != next_val) continue; // 提前剪枝下一步的数字

            int is_diagonal = (i % 2 != 0);

            int mx = 0, my = 0;

            if (is_diagonal) {

                mx = 2 * x + dx[i];

                my = 2 * y + dy[i];

                mid_visited[mx][my] = 1;

            }

            vis[tx][ty] = 1;

            path[path_len++] = i;

            int d = a[tx][ty];

            left[d]--;

            dfs(tx, ty, next_val);

            if (found) {

                // 恢复状态后直接返回

                vis[tx][ty] = 0;

                path_len--;

                left[d]++;

                if (is_diagonal) mid_visited[mx][my] = 0;

                return;

            }

            vis[tx][ty] = 0;

            path_len--;

            left[d]++;

            if (is_diagonal) mid_visited[mx][my] = 0;

        }

    }

}

int main() {

    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            scanf("%d", &a[i][j]);

            total[a[i][j]]++;

        }

    }

    if (!precheck()) {

        printf("-1\n");

        return 0;

    }

    memcpy(left, total, sizeof(left));

    left[a[0][0]]--;

    memset(vis, 0, sizeof(vis));

    memset(mid_visited, 0, sizeof(mid_visited));

    vis[0][0] = 1;

    dfs(0, 0, 0);

    if (found) printf("%s\n", ans);

    else printf("-1\n");

    return 0;

}