自己建网站的费用,响应式网站 手机版,邢台seo外包,史志部门建设网站 说明题目描述
小明冒充X星球的骑士#xff0c;进入了一个奇怪的城堡。城堡里边什么都没有#xff0c;只有方形石头铺成的地面。 假设城堡地面是 n x n 个方格。 按习俗#xff0c;骑士要从西北角走到东南角。可以横向或纵向移动#xff0c;但不能斜着走#xff0c;也不能跳跃…题目描述
小明冒充X星球的骑士进入了一个奇怪的城堡。城堡里边什么都没有只有方形石头铺成的地面。 假设城堡地面是 n x n 个方格。 按习俗骑士要从西北角走到东南角。可以横向或纵向移动但不能斜着走也不能跳跃。 每走到一个新方格就要向正北方和正西方各射一箭。城堡的西墙和北墙内各有 n 个靶子 同一个方格只允许经过一次。但不必走完所有的方格。 如果只给出靶子上箭的数目你能推断出骑士的行走路线吗 有时是可以的比如图中的例子。 本题的要求就是已知箭靶数字求骑士的行走路径测试数据保证路径唯一
输入 第一行一个整数N(0N20)表示地面有 N x 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
代码如下
#include iostream
#include cstring
using namespace std;
int dx[] {0,0,1,-1},dy[] {1,-1,0,0};//方向向量
const int N 21;
int mp[N][N];//存储地图编号
bool st[N][N];//标记地图某格是否走过或者能不能走
int path[410];//存储路径这个数组要开大一点它搜索的时候可能有一次搜索会把全部格子都走了
int n;
int flagx[N],flagy[N];//每走一格射的靶子用来判断与题目输入的靶子是否相同
int tarx[N],tary[N];//题目输入的靶子数目
int flagxs,flagys;
void PrintPath(int index)//输出结果函数也可以加入dfs中就是加进去的话代码比较丑
{for (int i 1;iindex;i){coutpath[i] ;}coutendl;
}void dfs(int x,int y,int index)//搜索路径
{if (xn yn)//判断是否到达终点{for (int i 1;in;i){if (flagx[i]tarx[i]) flagxs;if (flagy[i]tary[i]) flagys;}if (flagxsn flagysn)//判断到达终点后靶子数目是否相同{PrintPath(index);return ;}else{flagxs 0;flagys 0;return;}}for (int i 0;i4;i){int xx xdx[i],yy ydy[i];if (st[xx][yy]) continue;flagx[xx];flagy[yy];path[index1] mp[xx][yy];st[xx][yy] true;dfs(xx,yy,index1);st[xx][yy] false;flagx[xx]--;flagy[yy]--;}
}int main()
{cinn;for (int i 1;in;i) cintary[i];for (int i 1;in;i) cintarx[i];memset(st,1,sizeof(st));int k 0;for (int i 1;in;i)for (int j 1;jn;j){mp[i][j] k;st[i][j] false;}st[1][1] true;//标记起点flagx[1] 1;flagy[1] 1;path[1] 0;dfs(1,1,1);return 0;
}可惜这样暴搜超时了无法AC我们要想办法剪枝。
剪枝优化AC代码如下
#include iostream
#include cstring
using namespace std;int dx[] {0, 0, 1, -1}, dy[] {1, -1, 0, 0};
const int N 21;
int mp[N][N];
bool st[N][N];
int tarx[N], tary[N];
int n;
int sum;//这条路线的总步数
int path[410];void PrintPath(int index) {for (int i 1; i index; i) {cout path[i] ;}cout endl;
}void dfs(int x, int y, int index) {if (index sum)//当它搜索的时候超过总步数(多走了)就说明肯定不是走这条路所以重新选路return;for (int i 1; i n; i) {if (tarx[i] 0 || tary[i] 0)//当有靶子减没了也肯定是走错路了return;}if (x n y n sum index) {//只有刚好到终点且走的步数与总步数相等就说明是这条路了PrintPath(index);return ;}for (int i 0; i 4; i) {int xx x dx[i], yy y dy[i];if (st[xx][yy])continue;tary[yy]--;tarx[xx]--;st[xx][yy] true;//记得标记path[index 1] mp[xx][yy];dfs(xx, yy, index 1);st[xx][yy] false;//要记得还原现场tary[yy];tarx[xx];}}int main() {cin n;for (int i 1; i n; i) {cin tary[i];sum tary[i];}for (int i 1; i n; i)cin tarx[i];memset(st, 1, sizeof(st));int k 0;for (int i 1; i n; i)for (int j 1; j n; j) {mp[i][j] k;st[i][j] false;}st[1][1] true;tary[1]--;//注意刚开始要把(1,1)位置的靶子先减掉tarx[1]--;path[1] 0;dfs(1, 1, 1);return 0;
}
