蓝桥杯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
有输出结果

1 1
0
输出-1

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/guonei/2024-04-19/160325.html，文章来源：网络cs，作者：往北，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！