蓝桥杯2024年第十五届省赛真题-数字接龙

在这里插入图片描述

思路：DFS，因为输入的i，j的顺序导致，方向向量中x是行编号，y是列编号。方向向量可能和直觉上不同。

错的
//int dx[8]={0,1,1,1,0,-1,-1,-1};
//int dy[8]={1,1,0,-1,-1,-1,0,1};
对的
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0 , 1,1,1,0,-1,-1,-1};

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

const int N = 15;
int n,k;
int mp[N][N];
bool vis[N][N];
vector<int>ans;

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

//判断是否交叉
bool charge(int x,int y,int i){
    if(i%2)if(vis[x+dx[(i+1)%8]][y+dy[(i+1)%8]]&&vis[x+dx[(i-1)%8]][y+dy[(i-1)%8]])return true;
    return false;
}

void dfs(int x,int y,int z,int count){
    
    if(x==n-1&&y==n-1&&count==n*n-1){
        for(auto it:ans)cout<<it;cout<<endl;
        exit(0);
    }
    
    for(int i=0;i<8;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        //越界，访问情况，接龙，交叉需要判断
        if(nx>=0&&nx<=n-1&&ny>=0&&ny<=n-1&&vis[nx][ny]==false&&mp[nx][ny]==z&&!charge(x,y,i)){
            vis[nx][ny]=true;
            ans.push_back(i);
            count++;
            dfs(nx,ny,(z+1)%k,count);
            //回溯
            count--;
            vis[nx][ny]=false;
            ans.pop_back();
        }
    }
}

void solve(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    memset(mp, -1, sizeof(mp));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mp[i][j];
        }
    }
    //特殊情况
    if(n==1){
        cout<<-1;
        return;
    }
    vis[0][0]=true;
    //不能直接+1，k可能为1
    dfs(0,0,(mp[0][0]+1)%k,0);
    cout<<-1<<endl;
}

signed main(){
    int T=1;
    while(T--)solve();
    return 0;
}

特殊情况

10 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
有输出结果