建站优化收费/seo建站公司

问题描述

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为 N×N 的格子棋盘上展开，其中每一个格子处都有着一个 0…K−1 之间的整数。游戏规则如下：

1. 从左上角 (0,0) 处出发，目标是到达右下角 (N−1,N−1) 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。

2. 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0,1,2,…,K−1,0,1,2,…,K−1,0,1,2…0,1,2,…,K−1,0,1,2,…,K−1,0,1,2… 。

3. 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。

4. 路径中不可以出现交叉的线路。例如之前有从 (0,0) 移动到 (1,1) ，那么再从 (1,0) 移动到 (0,1) 线路就会交叉。

为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图 2 所示；因此行进路径可以用一个包含 0…7 之间的数字字符串表示，如下图 1 是一个迷宫示例，它所对应的答案就是：41255214。

现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 −1。

输入格式

第一行包含两个整数 N,K。

接下来输入 N 行，每行 N 个整数表示棋盘格子上的数字。

输出格式

输出一行表示答案。如果存在答案输出路径，否则输出 −1。

样例输入

3 3
0 2 0
1 1 1
2 0 2

样例输出

41255214

样例说明

行进路径如图 1 所示。

评测用例规模与约定

对于 80% 的评测用例：1≤N≤5 。

对于 100% 的评测用例：1≤N≤10,1≤K≤10 。

作者有话说 ：

啊啊啊，真的讨厌dfs，剪枝这类题，做了很多题，还是很难做对。。。又调了很久。。。。。

代码：

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
int n,k;
int dx[]={-1,-1,0,+1,+1,+1,0,-1};
int dy[]={0,+1,1,1,0,-1,-1,-1};
vector<vector<int> > v(15,vector<int>(15,-1));
bool f[15][15][15][15],g[15][15];
bool flag=false;
void dfs(int x,int y,string ans,int step)
{if(flag) return;if(step==n*n&&x==n-1&&y==n-1) {cout<<ans;flag=true;return;}for(int i=0;i<8;i++){int tx=x+dx[i];int ty=y+dy[i];if(tx<0||tx>=n||ty<0||ty>=n) continue;if(g[tx][ty]) continue; // 当前节点是否访问 if(v[tx][ty]==(v[x][y]+1)%k) { // 满足题意 if(i%2&&(f[x][ty][tx][y]||f[tx][y][x][ty])) continue; // 检查对角线 f[x][y][tx][ty]=true;f[tx][ty][x][y] = true;g[tx][ty]=true;dfs(tx,ty,ans+char(i+'0'),step+1);f[x][y][tx][ty]=false; // 回溯 f[tx][ty][x][y] = false;g[tx][ty]=false;} }}
int main()
{cin>>n>>k;g[0][0]=true;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>v[i][j];dfs(0,0,"",1);if(!flag) cout<<-1; return 0;
}