小航如愿以偿，以五百分的成绩，进入了c++佚名者学校。（详见 走进“深度搜索基础训练“，踏入c++算法殿堂（五）_aliyonghang的博客-CSDN博客）现在到了分班考试时间，同学们个个摩拳擦掌，准备考试。
“叮——”考试开始。
第一道题
题目：
1.迷宫问题 (Standard IO)
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述：
编辑
输入：
第一行输入n，表示n行n列的迷宫
接下来有n行，每行n个数，分别用1或0表示能否通过
输出：
输出路径数
样例输入：
3
0 0 0
0 1 1
1 0 0
样例输出：
2
小航想到（思路）：
1.可用搜索的方法来做（一条路走到黑），慢慢的尝试，直到达到终点
2.要用数组记录方法数
3.可以用两个一维或一个二维数组对位置进行变化（上下左右）
4.设立visit数组标记已走过某个点
5.设a数组记录迷宫，当a[x][y]==0时，标记并准备下一步；否则重新选择方向，直到找到或四种方向都已经试过
小航写道（程序）：
#include<iostream> using namespace std; int n,x1,y1,x2,y2,mi1[10][10],mi2[10][10],bx[9]={0,-1,0,1,-1,1,-1,0,1},by[9]={0,-1,-1,-1,0,0,1,1,1},s; void dg(int x,int y) { if(x==x2&&y==y2) { s++; return; } else { for(int i=1;i<=8;i++) { int qx=x+bx[i],qy=y+by[i]; if(qx>0&&qx<=n&&qy>0&&qy<=n) { if(mi1[qy][qx]==0&&mi2[qy][qx]==0) { cout<<qy<<" "<<qx<<endl; mi2[qy][qx]=1; dg(qx,qy); mi2[qx][qy]=0; } } } } } int main() { cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>mi1[i][j]; } } x1=1; y1=1; mi2[y1][x1]=1; x2=n; y2=1; dg(x1,y1); cout<<s; }
第二道题
题目：
2. 马的走法 (Standard IO)
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述：
在5X5的棋盘上，给定一位置，输出马回到原点有多少种不同的方案。
注意：马走的每一步必须在棋盘上，走斜日，如右图→：
编辑
输入：
给定一位置，x ,y,中间有一空格隔开。
输出：
输出可以回到原点的方案总数
样例输入：
1 1
样例输出：
61424
小航想到（思路）：
1.要用与上题不同的格式进行，因为起点就是终点。应使用如下格式：
void DFS(形式参数) { for(...) { if(满足条件) { 相应操作; if(到达终点) { 记录; } else DFS(...) 回溯； } } }
(第一次写伪代码，很烂，请谅解）
2.八种方向要记录（用一维数组或二维数组）
3.visit表记法也要用上！
小航写道（程序）：
#include<iostream> using namespace std; int t,fangx[10]={0,-2,-2,-1,-1,1,1,2,2},fangy[10]={0,-1,1,-2,2,-2,2,-1,1},b[10][10],qx,qy; void dg(int x1,int y1) { for(int i=1;i<=8;i++) { int nx=x1+fangx[i],ny=y1+fangy[i]; if(nx>=1&&nx<=5&&ny>=1&&ny<=5&&b[nx][ny]==0) { b[nx][ny]=1; if(nx==qx&&ny==qy) { t++; } else { dg(nx,ny); } b[nx][ny]=0; } } } int main() { cin>>qx>>qy; dg(qx,qy); cout<<t; }
第三道题：
题目：
1099. 【递归算法】棋子移动 (Standard IO)
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述：
有2n个棋子（n>=4）排成一行，开始位置为白子全部在左边，黑子全部在右边，如图（n=5）：00000*****
移动棋子的规则是：每次必须同时移动相邻两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为：__0*0*0*0*0*
输入：
仅输入黑棋和白棋的数目n（4<=n<=1000）。
输出：
以后各行输出每一步的移动结果，最后一行输出总步数。其中用’O’(大写字母)表示白棋，用’ * ’表示黑棋。’_”（下划线）表示一个空位。
样例输入：
5
样例输出：
OOOO_ _****O*
OOOO****_ _O*
OOO_ _***O*O*
OOO*O**_ _*O*
O_ _*O**OO*O*
O*O*O*_ _O*O*
_ _O*O*O*O*O*
step=7
小航想道（思路）：
1.请读者在评论区上填写，因为我太懒不想填写这样才能真正使读者成长。
小航写道(程序）：
#include<iostream> using namespace std; int n,space,sum; char a[2020]; void move(int s) { a[space]=a[s]; a[space+1]=a[s+1]; a[s]='_'; a[s+1]='_'; space=s; sum++; for(int i=1;i<=n*2+2;i++) { cout<<a[i]; } cout<<endl; } void digui(int m) { if(m==4) { move(4); move(8); move(2); move(7); move(1); } else { move(m); move(2*m-1); digui(m-1); } } int main() { cin>>n; for(int i=1;i<=n;i++) { a[i]='O'; a[i+n]='*'; } a[n*2+1]='_'; a[n*2+2]='_'; space=n*2+1; digui(n); cout<<"step="<<sum; }
因为这是级组里面的考试，所以并不是十分正规，这是等到比赛结束才能提交的。等待结束时，小航一直在检查（需要学习）……
“叮——”比赛结束，小航立刻提交。几分钟后，三百分（满分）显现在小航的电脑屏幕之上——小航全级第一（这几乎人人都是），被分到了六班！这是他梦寐以求的班级！
