过了几天,夏天来了。朝阳似火,炙烤大地;老师严肃,严格无比……
很快,一次“课堂测试”来了。(不过同学们都知道,这是一场考试)
同学们刚落座,测试就开始了。小航马上打开文档,读起题来。
第一道题
【搜索与回溯算法】泡泡龙 (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老师意味深长地说道。