商城网站案例,wordpress热点插件,建设网站需要租服务器吗,厦门seo网站优化题目描述
小明冒充X星球的骑士#xff0c;进入了一个奇怪的城堡。城堡里面什么都没有#xff0c;只有方形石头铺成的地面。 假设城堡的地面时n*n个方格。如下图所示。 按习俗#xff0c;骑士要从西北角走到东南角。可以横向或者纵向移动#xff0c;但是不能斜着走#x…题目描述
小明冒充X星球的骑士进入了一个奇怪的城堡。城堡里面什么都没有只有方形石头铺成的地面。 假设城堡的地面时n*n个方格。如下图所示。 按习俗骑士要从西北角走到东南角。可以横向或者纵向移动但是不能斜着走也不能跳跃。没走到一个新方格就要向正北方和正西方各射一箭。城堡的西墙和北墙内各有n个靶子同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目你能推断出骑士的行走路线吗有时是可以的比如上图中的例子。 本题的要求就是已知箭靶数字求骑士的行走的路径测试数据保证路径唯一。
输入描述
第一行一个整数N(0≤N≤20),表示地面有N*N个方格。 第二行N个整数空格分开表示北边的箭靶上的数字(自西向东) 第二行N个整数空格分开表示西边的箭靶上的数字(自北向南)
输出描述
输出一行若干个整数表示骑士路径。 为了方便表示我们约定每一个小格子用一个数字代表从西北角开始编号0,1,2,3… 比如上图中的方块编号为 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
样式输入
4
2 4 3 4
4 3 3 3样例输出
0 4 5 1 2 3 7 11 10 9 13 14 15题目分析
题目分析 本题是一个路径推断问题需要根据已知的箭靶数字来推断骑士在城堡内的行走路径。 首先我们需要理解题目中的规则和要求。骑士从西北角走到东南角每次移动到一个新的方格都需要向正北方和正西方各射一箭。每个方格只能经过一次且不需要走完所有的方格。 根据输入描述我们知道第一行输入是整数N表示地面有NxN个方格。第二行是北边箭靶上的数字表示自西向东的顺序。第三行是西边箭靶上的数字表示自北向南的顺序。 输出描述要求我们输出一行若干个整数表示骑士的路径。编号约定是从西北角开始编号0, 1, 2, 3… 思路 为了解决这个问题我们可以使用回溯法Backtracking来搜索所有可能的路径直到找到符合要求的路径为止。下面是解题思路的步骤 初始化一个N*N的矩阵用于记录每个方格是否被访问过。初始时将所有方格标记为未访问。 从起点00开始尝试向下或向右移动每次移动后更新当前位置并将对应的方格标记为已访问。 在每次移动后更新箭靶上的数字即向正北方和正西方各增加一箭的数量。 如果当前位置是终点N-1N-1则检查箭靶上的数字是否符合要求。如果符合要求则将当前路径加入结果列表。 如果当前位置不是终点继续尝试向下或向右移动重复步骤2-4。 当所有可能的路径都被尝试过后返回结果列表中的第一个有效路径作为最终答案。
代码
#include bits/stdc.h
using namespace std;
const int N21;
int row[N],col[N]; // 定义行和列的数组
int n; // 定义矩阵的大小
int dx[]{-1,0,1,0},dy[]{0,-1,0,1}; // 定义四个方向的偏移量
vectorint path; // 用来存储路径
bool st[N][N]; // 定义状态数组用于记录每个位置是否已经访问过// 深度优先搜索函数
bool dfs(int x,int y)
{if(xn-1 yn-1) // 如果到达终点{for(int i0;in;i)if(row[i]!0 || col[i]!0) // 如果还有未访问的行或列返回falsereturn false;return true; // 否则返回true}for(int i0;i4;i) // 遍历四个方向{int axdx[i],bydy[i]; // 计算下一个位置的坐标if(a0 || an || b0 || bn || st[a][b]) continue; // 如果越界或者已经访问过跳过if(row[a]0 || col[b]0) continue; // 如果该位置无法访问跳过st[a][b]true; // 标记该位置已访问row[a]--,col[b]--; // 更新行和列的剩余数量path.push_back(a*nb); // 将该位置加入路径if(dfs(a,b)) return true; // 如果找到一条路径返回truest[a][b]false; // 回溯恢复该位置的状态row[a],col[b]; // 恢复行和列的剩余数量path.pop_back(); // 回溯将该位置从路径中移除}return false; // 如果四个方向都无法继续前进返回false
}int main()
{cinn; // 输入矩阵的大小for(int i0;in;i) cincol[i]; // 输入列的数量for(int i0;in;i) cinrow[i]; // 输入行的数量col[0]--,row[0]--; // 将起点的行列数量减一st[0][0]true; // 标记起点已访问path.push_back(0); // 将起点加入路径dfs(0,0); // 从起点开始深度优先搜索for(auto x:path) coutx ; // 输出路径return 0;
}
