优美蓝桥杯

本题暴搜
核心剪枝就是，当第一次搜到终点的时候就返回，不需要再遍历其他的边了

具体就体现在 dfs 返回的是 bool 值

还有一点就是，一开始对对角线判断的时候，如果的是判断 左 和 上 （假设目标点是 左上 ）
就会出现一种情况，就是 左 和 上 的点已经走过，但是并没有连线，此时按照这个逻辑就会出错

如图：

剩下就是理清楚题目的遍历条件就可以了（路径重复和 k 的顺序）

#include<bits/stdc++.h>

using namespace std;

int n, k;

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

vector<vector<int>> g(12, vector<int>(12, -1));
vector<vector<bool>> st(12, vector<bool>(12, 1));

bool edge[12][12][12][12]; // edge[x][y][i][j] 表示有一条从 (x,y) -> (i,j) 的边

bool dfs(int x, int y, string sum, int step)
{
    if(step == n * n && x == n && y == n)
    {
        cout<<sum<<endl;
        return true; // 遇到答案就输出，然后立刻返回
    }

    for(int i = 0; i < 8; i++) // 由于按顺序遍历，所以确保了答案一定是按照字典序排布的
    {
        int tx = x + dx[i], ty = y + dy[i];
        if(st[tx][ty] == 1) // 重复路径
            continue;

        if(g[tx][ty] == (g[x][y] + 1) % k) // k 顺序
        {
            // if(i % 2 && st[x][ty] && st[tx][y])  败笔
            //     continue;

            if(edge[x][ty][tx][y] || edge[tx][y][x][ty]) // 对角判断
                continue;

            edge[x][y][tx][ty] = 1;
            st[tx][ty] = 1;

            if(dfs(tx, ty, sum + (char)('0' + i), step + 1))
                return 1;

            st[tx][ty] = 0;
            edge[x][y][tx][ty] = 0;
        }
    }

    return 0;
}

int main()
{
    n = 0, k = 0;
    cin>>n>>k;


    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            cin>>g[i][j];
            st[i][j] = 0;
        }
    st[1][1] = 1;
    if(!dfs(1, 1, "", 1))
        cout<<-1<<endl;

    return 0;
}