您现在的位置是：首页 >其他 >15届蓝桥杯c/c++b组试题F:数字接龙网站首页其他

题目:

问题描述

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

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

2. 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：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 。

运行限制

分析：

        从题目和数据规模可以肯定，这是一个搜索问题，我们可以递归和回溯来搜索路径，只要满足题目中给出的条件和限制，我们就选择这个路径点。现在来归纳以下限制条件：

        1、要求我们从(0,0)到(n-1,n-1)并且经过所有的点。

        2、要求经过的路径点是以0到K-1,0到K-1的顺序依次经过。

        3、要求搜索的路径不能出现交叉。

        4、没有解则输出-1.

        5、如果有多个解，那么输出字典序最小结果。

        对于限制条件1、2、4、5都比较好实现，这里着重讲一下条件3交叉问题：

方向数组

int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};

我们用上述数组与对应x,y的加和计算出下一个路径点的坐标，也就是：

int bx = x + dx[i];
int by = y + dy[i];

交叉问题

        对于路径的搜索，很容易想到图的遍历，它用visit数组来表示是否访问过，若访问过则值为1；一开始我用visit数组来表示是否访问过，但是发现不能用简单的对角线是否都被访问来表示一条路径，如下图：

        如果用对角线都被访问过表示一条路径，那么红色的线会被判为交叉线。

        所以这里我用的path数组来存储路径点的下一个路径的方向，也就是八个方向的编号，从0到7。因为判断交叉的方向只有（1，3，5，7）四个方向，所以我们就单独讨论这四个方向的路径信息。path数组初始值为-1表示没有路径，若为0到7，则表示访问过。

        这里我们用其中方向3为例子:

(x,y)是当前路径点，(bx,by)是下一个路径点，在路径选择是，判断当前路径点的相邻节点之间是否有路径，如图所示，(x+1,y)和(x,y+1)虽然被访问过，但之间没有路径。所以可以选择此方向。

但是如图所示的(x,y+1)有方向为5的路径，那么(x,y)不能选择方向3，会出现交叉线。

具体思路

        如果我们搜索到了结果，则选择字典序较小的进行更新；

        遍历八个方向，如果下一个路径点坐标超出范围，直接跳过；如果下一个路径点被访问过、或者出现了交叉线，直接跳过；如果下一个路径点的值是按顺序出现，那么对当前路径点的path的值赋值相应的方向编号，递归调用，回溯。

        递归函数dfs（int x,int y,string s,int pre,int dep）

        (x,y)是当前路径点，s为存储路径方向的字符串，pre保证搜索出的路径点的值是按顺序搜索的，dep为递归深度，只有dep为n*n时，才能保证所有路径点都搜索了一遍。

代码：

#include<iostream>
#include<string>
using namespace std;
const int N = 20;
int a[N][N];
int path[N][N];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
int n,k;
string res;
void dfs(int x,int y,string s,int pre,int dep){
	if(x == n && y == n && dep == n*n){
		if(res.empty()) res = s;
		else res = min(res,s);
		return;
	}
	for(int i=0;i<8;i++){
		int bx = x + dx[i];
		int by = y + dy[i];
		if(bx < 1 || bx > n || by < 1 || by > n) continue;
		if(path[bx][by] != -1) continue;
		if(i == 1 && (path[x-1][y] == 3 || path[x][y+1] == 7)) continue;
		else if(i == 3 && (path[x+1][y] == 1 || path[x][y+1] == 5)) continue;
		else if(i == 5 && (path[x][y-1] == 3 || path[x+1][y] == 7)) continue;
		else if(i == 7 && (path[x-1][y] == 5 || path[x][y-1] == 1)) continue;
		if(a[bx][by] < k && a[bx][by] == pre+1 || (pre+1) == k && a[bx][by] == 0){
			path[x][y] = i;
			dfs(bx,by,s+to_string(i),a[bx][by],dep+1);
			if(!res.empty()) return;
			path[x][y] = -1;
		}
	}
}
int main(){
	cin >> n >> k;
	for(int i=1;i<=n;i++){
		for(int j=1; j<=n; j++){
			cin >> a[i][j];
			path[i][j] = -1;
		}
	}
	string emp;
	dfs(1,1,emp,0,1);
	if(res.empty()) cout << -1;
	else cout << res;
	return 0;
}