打卡信奥刷题（3380）用C++实现信奥题 P9795 [NERC 2018] Easy Chess

P9795 [NERC 2018] Easy Chess

题目背景

翻译自 NERC 2018 E 题。

题目描述

Elma 正在学习象棋。

Elma 是个新手，她还不特别了解象棋是如何下的，所以，为了更好地让她了解象棋，她的奶奶让她从一个棋盘（如下图）中进行n nn次移动，每次移动只能是水平或垂直地移动若干个格子的，且每个点只能到达一次，使得从 a1 到 h8 处。

输入格式

输入一个数n ( 2 ≤ n ≤ 63 ) n(2 \leq n \leq 63)n(2≤n≤63)，表示你一共需要走的步数。

输出格式

给出一种可行方案且保证停留过的点不重复。

输入输出样例 #1

输入 #1

4

输出 #1

a1 f1 c1 c8 h8

说明/提示

对于所有数据保证2 ≤ n ≤ 63 2 \leq n \leq 632≤n≤63且保证存在至少一种合法方案。

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,cnt,step[70][5];//记录答案boolmp[10][10];//表示是否访问过boolflag;//标记结束intdx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};voiddfs(intx,inty){if(x==8&&y==8&&cnt==n){for(inti=1;i<=n;i++){//输出答案charc='a'+(char)(step[i][1]-1);//因为答案中我们存储的是整型，所以要转化为相应字符cout<<c<<step[i][2]<<" ";}flag=1;//标记已经找到答案，也可以使用 exist(0)return;}if(cnt==n)return;//当步数超过时返回for(inti=1;i<=4;i++){//枚举方向for(intj=1;j<=7;j++){//枚举移动长度intkx=x+dx[i]*j,ky=y+dy[i]*j;if(kx>8||kx<1||ky>8||ky<1)continue;//排除越界情况if(mp[kx][ky]==0){//没有被访问mp[kx][ky]=1;cnt++;step[cnt][1]=kx,step[cnt][2]=ky;dfs(kx,ky);cnt--;mp[kx][ky]=0;if(flag==1)return;//已经找到答案，可以继续返回}}}return;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//快读cin>>n;cout<<"a1 ";//先输出第一个位置mp[1][1]=1;//注意预处理第一个位置dfs(1,1);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容