过了几天，夏天来了。朝阳似火，炙烤大地；老师严肃，严格无比……
很快，一次“课堂测试”来了。（不过同学们都知道，这是一场考试）
同学们刚落座，测试就开始了。小航马上打开文档，读起题来。
第一道题
【搜索与回溯算法】泡泡龙 (Standard IO)
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述：
这是一个简化版的网络游戏：在一个N×N方块构成的棋盘中，每个方块均涂上红、黄、蓝、绿（记为l、2、3、4）中的一种颜色，游戏者可以在最底行任意找一个方块，用鼠标双击这个方块，于是该方块及与之相邻（即在上、下、左、右四个方向上有公共边）的所有的同色方块均被消掉，而因下方失去支持的方块将会自由落下填补空位。样例中给出一个4×4的棋盘样例，当游戏者双击最底层左边第二个方块后，将会形成输出结果的布局。
你的任务是编写一个泡泡龙模拟程序，对于给定的一个初始棋盘，计算游戏者双击最底层某个方块后棋盘的布局将会如何。
输入：
第1行有两个正整数N和M(I≤M≤N≤I00)，其中N表示棋盘的规模，而M则表示游戏者将双击最底层从左边数起的第M个方块。接下来的N行每行有N个l～4的整数组成，表示一个初始的棋盘，同一行相邻两个数之间用一个空格隔开。
输出：
N行，每行用N个数给出游戏结束后棋盘的布局，没有方块的格子用0表示，同一行相邻两个数之间也用一个空格分开。每行末尾有空格
样例输入：
4 2
1 2 3 4
4 2 4 4
3 4 4 3
1 4 4 3
样例输出
1 0 0 0
4 0 0 0
3 2 0 3
1 2 3 3
小航想道（思路）：
1.这是道题目主体游戏，所以主题思路应该在与模拟。
2.输入以后，首先应通过搜索（可以用递归的方法开展搜索）来去掉方块（只要符合条件，将他们设置为零即可）【条件：在地图的范围之内，方块颜色与玩家所点击的方块颜色相同】
3.之后，可以另设一个数组，进行“去零操作”（用for循环实现）。
小航写道（代码）：
#include<iostream> using namespace std; int n,m,a[105][105],b[105][105],fx[5]={0,-1,0,0,1},fy[5]={0,0,-1,1,0},visit[105][105]; void dg(int x,int y,int num) { for(int i=1;i<=4;i++) { int nx=x+fx[i],ny=y+fy[i]; if(a[nx][ny]==num&&visit[nx][ny]==0) { visit[nx][ny]=1; a[nx][ny]=0; dg(nx,ny,num); visit[nx][ny]=0; } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>a[i][j]; } } int nu=a[n][m]; a[n][m]=0; dg(n,m,nu); int t; for(int i=1;i<=n;i++) { t=n; for(int j=n;j>=1;j--) { if(a[j][i]!=0) { b[t][i]=a[j][i]; t--; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cout<<b[i][j]<<" "; } cout<<endl; } }
第二道题
跳马问题
在n×m棋盘上有一中国象棋中的马，规定：
- 马走日字；
- 马只能往右走。
要求马可以从棋盘的左下角（1，1）走到右上角（n，m）。请你编写程序，输出一条可行的路径。
输入
输入两个正整数n和m，表示棋盘的大小为n*m。
输出
输出一条可行的路径，用行列下标表示，并用“->”连接。
样例输入
9 5
样例输出
(1,1)->(3,2)->(5,1)->(6,3)->(7,1)->(8,3)->(9,5)
小航想道（思路）：
1.马会有四种方向行走（本来有八种方向，但是题目要求只能往右走，因此就只剩下四种方向了），可以用以为或二维数组储存。
2.可以用深度优先搜索的方式实现，在过程中用二维数组储存路线，记得要回溯！
3.结束搜索（到达重点【右上角】）时，可以直接输出。输出后，题目的任务就完成了，可以用“exit（0）”来强制结束程序。
小航写道（程序）
注：本次的程序有详细注释，欢迎提建议
#include<iostream> using namespace std; int n,m,a[105][3],visit[70][70],step=1; int fx[5]={0,-1,-2,2,1},fy[5]={0,-2,-1,1,2}; void dfs(int x,int y) { if(x==m&&y==n) { for(int i=1;i<=step-2;i++) { cout<<"("<<a[i][1]<<","<<a[i][2]<<")->";//按照输出格式 } cout<<"("<<x<<","<<y<<")"; exit(0);//强制结束程序 } for (int i=1;i<=4;i++) { int nx=x+fx[i],ny=y+fy[i];//下一步可能在此点 if(nx>=1&&nx<=m&&ny>=1&&ny<=n&&visit[nx][ny]==0)//判断是否可以继续走 { a[step][1]=nx; a[step][2]=ny;//记录步骤 step++; visit[nx][ny]=1;//标记，防止重复 dfs(nx,ny);//dg（递归） visit[nx][ny]=0; step--;//回溯 } } } int main() { cin>>m>>n; a[step][1]=1; a[step][2]=1;//初始位置也要记录 step++; visit[1][1]=1;//标记 dfs(1,1); }
很快，”课堂小测“结束，小航赶紧提交了程序，刷新了界面，两个绿油油、让人看上去无比惬意的AC显现出来……
“同学们，你们掌握得还不错”，接着，下课铃响了。
“现在，你们要学的越来越多，学习任务更紧更多了，学习更加辛苦了，就如同夏天烈日。但是，坚持一下，烈日将变为暖阳，照亮你们的程序人生”看着快速收拾书包的同学们，TL老师意味深长地说道。
