60 lines
1.8 KiB
C++
60 lines
1.8 KiB
C++
// lanqiao 19712 数字接龙
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 20;
|
|
int a[N][N]; // 迷宫数组
|
|
int vis[N][N]; // 标记数组
|
|
int n, k;
|
|
// 方向数组 0 1 2 3 4 5 6 7
|
|
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
|
|
int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1};
|
|
string res; // 结果字符串
|
|
|
|
// x, y为搜索的位置坐标, pre 前一个访问位置的数字, s 当前路径的访问序列, dep 搜索的深度
|
|
void dfs(int x, int y, int pre, string s, int dep){
|
|
if(x == n && y == n && dep == n*n){
|
|
if(res.empty()) res = s; // 字典需最小的
|
|
return;
|
|
}
|
|
for(int i = 0; i < 8; i++){
|
|
int bx = x + dx[i], by = y + dy[i];
|
|
if(bx < 1 || bx > n || by < 1 || by > n) continue;
|
|
if(vis[bx][by]) continue;
|
|
// 防止交叉搜索
|
|
if(i == 1 && vis[x-1][y] && vis[x][y+1]) continue;
|
|
else if(i == 3 && vis[x+1][y] && vis[x][y+1]) continue;
|
|
else if(i == 5 && vis[x+1][y] && vis[x][y-1]) continue;
|
|
else if(i == 7 && vis[x-1][y] && vis[x][y-1]) continue;
|
|
// 保证路径数值为0 1 ... k-1
|
|
if((a[bx][by] < k && a[bx][by] == pre + 1) || (pre + 1 == k && a[bx][by] == 0)){
|
|
vis[bx][by] = 1;
|
|
dfs(bx, by, a[bx][by], s + to_string(i), dep + 1);
|
|
|
|
// 最优性剪枝, 已经找到了一个可行序列, 不必再往后搜索
|
|
if(!res.empty()) return;
|
|
vis[bx][by] = 0; //回溯
|
|
}
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
cin >> n >> k;
|
|
for(int i = 1; i <= n; i++){
|
|
for(int j = 1; j <= n; j++){
|
|
cin >> a[i][j];
|
|
}
|
|
}
|
|
string emp;
|
|
vis[1][1] = 1;
|
|
dfs(1, 1, 0, emp, 1);
|
|
if(res.empty()) cout << -1 << endl;
|
|
else cout << res << endl;
|
|
return 0;
|
|
}
|
|
|
|
/* test samples -> 41255214
|
|
3 3
|
|
0 2 0
|
|
1 1 1
|
|
2 0 2
|
|
*/ |