蓝桥杯 数字接龙 深度优先搜索 dfs C++

问题描述

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为 N x 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… 。

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。 

算法思路

完整代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
const int N=11;
int a[N][N];
vector<int> path;//存储路径 
int visited[N][N];//表示是否访问过 
int edge[N][N][N][N];//表示是否有交点 
int dirs[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};//八个方向 
bool dfs(int row,int col)
{
	if(row==n-1&&col==n-1)//到达终点，检查路径长度是否等于n*n-1 
	{
		return path.size()==n*n-1;
	}
	for(int d=0;d<8;d++)//遍历8个方向 
	{
		int row1=row+dirs[d][0];
		int col1=col+dirs[d][1];
		if(row1<0||row1>=n||col1<0||col1>=n)//出边界 
		{
			continue;
		}
		if(visited[row1][col1])//已经访问过 
		{
			continue;
		}
		//假设k=2，变化规律就变成0,1,0,1...
		//当a[row][col]=0时，a[row1][col1]就应该为1
		//当a[row][col]=1时，a[row1][col1]就应该为0
		//所以a[row1][col1]==(a[row][col]+1)%k 
		if(a[row1][col1]!=(a[row][col]+1)%k)
		{
			continue;
		}
		if((d%2!=0)&&(edge[row][col1][row1][col]||edge[row1][col][row][col1]))//检查斜路径，如图所示 
		{
			continue;
		}
		//访问 
		visited[row1][col1]=1;
		edge[row][col][row1][col1]=1;
		path.push_back(d);
		if(dfs(row1,col1))
		{
			return true;
		}
		//回溯 
		path.pop_back();
		visited[row1][col1]=0;
		edge[row][col][row1][col1]=0;
	}
	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];
		}
	}
	visited[0][0]=1;//初始化起点已访问 
	if(dfs(0,0))
	{
		for(int i=0;i<path.size();i++)
		{
			cout<<path[i];
		}
	}else{
		cout<<"-1"<<endl;
	}
	return 0;
}