【蓝桥杯】：蓝桥杯之路径之谜
- 题目分析
- 这是一道路径谜题，描述了一个骑士在一个(n\times n)方格组成的城堡中行走的问题。
- 骑士从西北角（入口）走到东南角（出口），可以横向或纵向移动，但不能斜着走，也不能跳跃。
- 每走到一个新方格，要向正北方和正西方各射一箭，城堡的西墙和北墙各有(n)个靶子。
- 同一个方格只允许经过一次，题目要求根据靶子上箭的数目推断骑士的行走路线。
- 解题思路
- 可以使用深度优先搜索（DFS）来解决这个问题。
- 从入口开始，尝试向四个方向（东、南、西、北）移动，每次移动到一个新方格时，检查是否满足条件（不能斜着走，不能跳跃，同一个方格只允许经过一次）。
- 每移动到一个新方格，记录下对靶子的影响（正北方和正西方的靶子箭数加1）。
- 如果移动到的方格是出口，且靶子上的箭数与题目给出的一致，则找到了一条可行的路径。
- 如果在某一步无法继续移动（所有方向都不符合条件），则需要回溯到上一步，尝试其他方向。
- 深度优先遍历（DFS）思想
- 基本概念
- 深度优先遍历是一种图（或树）的遍历算法。它从起始节点开始，沿着一条路径尽可能深地探索下去，直到无法继续或达到目标，然后回溯到上一个未完全探索的节点，继续探索其他路径。
- 实现方式
- 通常使用递归或栈来实现。在递归实现中，函数会不断调用自身来深入探索图的节点，直到达到终止条件。在栈实现中，将节点压入栈中，每次从栈顶取出节点进行探索。
- 应用场景
- 常用于寻找图中的路径、连通分量、拓扑排序等问题。在本题中，用于寻找骑士在城堡中的可行路径。
- 基本概念
- 回溯思想
- 基本概念
- 回溯是一种在搜索过程中进行剪枝的技术。当发现当前路径不可能达到目标时，回退到上一个状态，尝试其他可能的路径。
- 实现方式
- 在搜索算法中，当遇到不满足条件的情况时，撤销当前操作，返回到上一步操作的状态，然后尝试其他选择。
- 应用场景
- 常用于解决组合优化问题、迷宫问题、数独问题等。在本题中，当骑士走到一个无法继续前进的方格时，需要回溯到上一个方格，尝试其他方向的移动。
- 基本概念
通过以上思路和算法思想，可以尝试编写代码来解决这道路径谜题。
#include<iostream>
#include<vector>
//#include<bits/stdc++.h>
int n, a[25], b[25], k1, k2;
//定义一个二维数组标记上下左右;
const int v[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
//int flag;//标记默认为0;
int flag;
int vis[25][25], num, s[600];
using namespace std;
//实现我们的dfs;
void dfs(int x, int y, int k)
{
//判断边界情况1;
if (x < 1 || y < 1 || x > n || y > n)
{
return;
}
//判断边界情况2;b[x]表示行数没有走过;a[y]表示列数没有没走过;
//if (b[x] < 0 || a[y] || flag == 1)
//{
// return;
//}
if (b[x] < 0 || a[y] < 0 || flag == 1)//防止我们误判当前没有越过起点;
{
return;
}
//成功的情况下;
s[k] = (x - 1) * n + (y - 1);
//找到答案就返回;
if (x == n && y == n && k1 == 1 && k2 == 1)
{
//正难则反;从终点倒推到起点的(k1==1&&k2==1)的位置;
//不要去想展开图 我们相信我们走到这一步已经完成了我们的走到终点的目的;
flag = 1;
num = k;//num变量存储我们的k步;
return;
}
for (int i = 0; i < 4; i++)
{
int xx = x + dx[i], yy = y + dy[i];//上下左右遍历矩阵;
if (vis[xx][yy])
//如果这个点已经走过了则跳过当前点;
{
continue;//如果这个点遍历过则跳过该点(题目要求);
}
b[xx]--;
a[yy]--;
k1--;
k2--;
vis[xx][yy] = 1;//标记此点已经被遍历过了;
dfs(xx, yy, k + 1);//从下一个点继续遍历;
//恢复现场;
b[xx]++;
a[yy]++;
k1++;
k2++;
vis[xx][yy] = 0;//标记为false重新遍历;
}
}
//void dfs(int x, int y, int k) //常规dfs搜索模板;
//{
// if (x < 1 || y < 1 || x > n || y > n) return; //判断越界;
// //if (b[x] < 0 || a[y] < 0 || flag == 1) return; //不符合题意或找到答案了就返回;
// //坐标索引公式:假设矩阵的大小是 n* m 那么对于位置(x, y) 其在一维数组中的索引可以通过公式 index = x * m + y 来计算;
// s[k] = (x - 1) * n + (y - 1); //记录路径，(编号可用坐标表示为i*m+j，m为列数);
// if (x == n && y == n && k1 == 1 && k2 == 1) //找到答案就返回;
// {
// num = k;
// return;
// //不要去想展开图 我们相信我们走到这一步已经完成了我们的走到终点的目的;
// }
// for (int i = 0; i < 4; i++) //查找右左下上;
// {
// int xx = x + v[i][0];
// int yy = y + v[i][1];
// if (vis[xx][yy] == 1) continue; //该点走过，跳过;
// b[xx]--;
// a[yy]--;
// k1--;
// k2--;
// vis[xx][yy] = 1;
// dfs(xx, yy, k + 1);
// b[xx]++; //回溯，还原值;
// a[yy]++;
// k1++;
// k2++;
// vis[xx][yy] = 0;
// }
//}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
k1 += a[i];//记录每列要走的总数;
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
k2 += b[i];;
}
flag = 0;
vis[1][1] = 1;//第一个位置的坐标为true;
dfs(1, 1, 1);//dfs深度优先遍历从第一个坐标开始遍历;
for (int i = 1; i <= num; i++)
{
cout << s[i] << " ";
}
return 0;
}