网站建设 保障接单 计划,网站建设试题,阿里云数据库主机wordpress,网页制作题用什么软件[蓝桥杯 2016 国 AC] 路径之谜
题目描述
小明冒充 X X X 星球的骑士#xff0c;进入了一个奇怪的城堡。
城堡里边什么都没有#xff0c;只有方形石头铺成的地面。
假设城堡地面是 n n n\times n nn 个方格。如图所示。 按习俗#xff0c;骑士要从西北角走到东南角。 …[蓝桥杯 2016 国 AC] 路径之谜
题目描述
小明冒充 X X X 星球的骑士进入了一个奇怪的城堡。
城堡里边什么都没有只有方形石头铺成的地面。
假设城堡地面是 n × n n\times n n×n 个方格。如图所示。 按习俗骑士要从西北角走到东南角。
可以横向或纵向移动但不能斜着走也不能跳跃。
每走到一个新方格就要向正北方和正西方各射一箭。
城堡的西墙和北墙内各有 n n n 个靶子
同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目你能推断出骑士的行走路线吗
有时是可以的比如如图中的例子。
本题的要求就是已知箭靶数字求骑士的行走路径测试数据保证路径唯一
输入格式
第一行一个整数 N ( 0 N 20 ) N(0N20) N(0N20)表示地面有 N × N N \times N N×N 个方格。
第二行 N N N 个整数空格分开表示北边的箭靶上的数字自西向东
第三行 N N N 个整数空格分开表示西边的箭靶上的数字自北向南
输出格式
一行若干个整数表示骑士路径。
为了方便表示我们约定每个小格子用一个数字代表从西北角开始编号 $:0,1,2,3 \cdots $。
比如图中的方块编号为
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15样例 #1
样例输入 #1
4
2 4 3 4
4 3 3 3样例输出 #1
0 4 5 1 2 3 7 11 10 9 13 14 15提示
时限 1 秒, 256M。蓝桥杯 2016 年第七届国赛 众所周知蓝桥杯奖水题不水 经过两个小时的折磨终于做出来了网上的题解能不能先把题目过了再发。。 使用dfs运用减枝开四个数组来标记然后就是dfs常规的了但是题目各种细节使人心力交瘁 #includebits/stdc.h
using namespace std;
const int N25;
int g[N][N];
bool vis[N][N];
int path[450];
int n,cnt,k;
bool f;
int ax[N],ay[N];
int bx[N],by[N];
int dx[4] {-1, 0, 1, 0};
int dy[4] {0, 1, 0, -1};
bool check()
{for(int i1;in;i){if(bx[i]!ax[i]||by[i]!ay[i])return 0;}return 1;
}void dfs(int x,int y)
{if(f) return ;if(xnyncheck()){for(int i0;icnt;i)coutpath[i] ;f1;return;}for(int i0;i4;i){int xxxxdx[i],yyyydy[i];if(vis[xxx][yyy]||xxx1||xxxn||yyy1||yyyn||bx[xxx]ax[xxx]||by[yyy]ay[yyy])continue;bx[xxx] ;by[yyy] ;vis[xxx][yyy]true;path[cnt]g[xxx][yyy];dfs(xxx,yyy);bx[xxx] --;by[yyy] --;vis[xxx][yyy]false;path[cnt--]-1; }}
int main()
{cinn;for(int i1;in;i)cinay[i];for(int i1;in;i)cinax[i];for(int i1;in;i){for(int j1;jn;j){g[i][j]k;}}vis[1][1]true;path[0]0;cout0 ;bx[1]1,by[1]1;dfs(1,1);return 0;
}
