第十五届蓝桥杯：dfs之数字接龙

#include <iostream> using namespace std; const int N = 300; int a[N][N];//存值 int b[N][N];//判断某个点是否出现过 int n,k; string path; int dx[] = {-1,-1,0,1,1,1,0,-1}; int dy[] = {0,1,1,1,0,-1,-1,-1}; bool dfs(int x,int y,int cur,int pos) { if(pos == n*n && x == n-1 && y== n-1) { cout << path << endl; return true; } for(int i = 0;i<=7;i++) { int bx = x+dx[i]; int by = y+dy[i]; if(b[bx][by]) continue; if(bx<0 || bx>n-1 || by<0 || by>n-1) continue; if(((cur == k-1) && (a[bx][by] != 0)) || (cur < k-1 && a[bx][by] != cur+1)) continue; if(i==1&&b[bx][by-1]&&b[bx+1][by]) continue; else if(i==3&&b[bx-1][by]&&b[bx][by-1]) continue; else if(i==5&&b[bx-1][by]&&b[bx][by+1]) continue; else if(i==7&&b[bx+1][by]&&b[bx][by+1]) continue; b[bx][by] = 1; path+=to_string(i); if(dfs(bx,by,a[bx][by],pos+1))return true; b[bx][by] = 0; path.pop_back(); } return false; } int main() { cin >> n >> k; for(int i = 0;i<n;i++) { for(int j = 0;j<n;j++) { cin >> a[i][j]; } } b[0][0] = 1; if(!dfs(0,0,a[0][0],1)) cout << -1 << endl; return 0; }