蓝桥/15/B/4 数字接龙

点击查看代码

#include<bits/stdc++.h>
using namespace std;int n,k,a[15][15];
bool vis[15][15],cross[15][15];
vector<int> path;int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};bool dfs(int x,int y,int cnt)
{if(x==n-1&&y==n-1){return cnt==n*n;}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]) continue;if (a[nx][ny] != (a[x][y] + 1) % k) continue;bool diag=i&1;int cx=min(x,nx),cy=min(y,ny);if(diag&&cross[cx][cy]) continue;vis[nx][ny]=1;if(diag) cross[cx][cy]=1;path.push_back(i);if(dfs(nx,ny,cnt+1)) return true;vis[nx][ny]=0;if(diag) cross[cx][cy]=0;path.pop_back();}return false;}int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>k;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}vis[0][0]=1;if(dfs(0,0,1)){for(int &p : path){cout<<p;}}else{cout<<"-1"<<"\n";}return 0;
}