算法题--小游戏
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法题--小游戏,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2803字,纯文字阅读大概需要5分钟。
内容图文
![算法题--小游戏](/upload/InfoBanner/zyjiaocheng/839/fd4185dc52fe49608ad38b08919f4f1c.jpg)
题目传送门https://blog.csdn.net/NNNNNNNNNNNNY/article/details/51592641?utm_source=blogxgwz6
递归与回溯
//这个程序是用来判断一个棋盘上给定的两个点相连的最短路径
//使用递归和回溯法求解
#include <stdio.h>
#include <memory.h>
#define MAXIN 75
char board[MAXIN + 2][MAXIN + 2]; //定义矩形板
//to的四个方向分别代表 下 右 上 左
//w是行数,h是列数
int minstep, w, h, to[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
char dir[4][6] = {"down", "right", "up", "left"};
bool mark[MAXIN + 2][MAXIN + 2]; //定义标记数组
void Search(int now_x, int now_y, int end_x, int end_y, int step, int f){
//递归的结束条件
if(f!=-1)
printf("start, step=%d, %s, (%d, %d), (%d, %d)\n", step, dir[f], now_x, now_y, end_x, end_y);
if(step > minstep) {return;} //如果是比最小步数大的话那么就不用继续走下去了
if(now_x == end_x && now_y == end_y){//到达终点
if(minstep > step) minstep = step;//目标就是更新最小步数,这是个全局变量
return; //到达终点了也要返回
}
//接下来递归地枚举所有可能的情况
//i的值对应的方向 0 1 2 3
// 下 右 上 左
for(int i=0; i<4; i++){ //枚举下一步的方向
int x = now_x + to[i][0];
int y = now_y + to[i][1];
//判断该位置是否有效
//要求不能越界并且(要么可以走,要么已经到终点并且这个地方是一个牌)
if((x>-1) && (x<w+2) && (y>-1) && (y<h+2) && (((board[y][x]==' ') &&
(mark[y][x]==false))||((x==end_x) && (y==end_y) && (board[y][x]=='X')))){
//看看是否和上一次的方向一样,如果一样的话那么step不变,否则要加一
printf("go: %s\n", dir[i]);
mark[y][x] = true;
if(f==i) Search(x,y,end_x,end_y,step,i);//一开始i肯定不等于-1所以一开始要加一
else Search(x,y,end_x,end_y,step+1,i);
//然后回溯,这块地方要标记成没走过
mark[y][x] = false;
}
}
if(f!=-1)
printf("end step=%d, %s, (%d, %d), (%d, %d)\n", step, dir[f], now_x, now_y, end_x, end_y);
}
int main(){
int Boardnum = 0; //记录这是第几号棋盘
while(scanf("%d %d", &w, &h)){//读入棋盘的宽和高
if(w==0 && h==0) break; //遇到 0 0 的输入就退出循环
Boardnum++;
printf("Board#%d:\n", Boardnum);
int i,j;
//初始化第0行和第0列所有元素
for(i=0; i<MAXIN+2; i++) board[0][i]=board[i][0]=' ';
for(i=1; i<=h; i++){//读入矩形板的布局
getchar();//吸收回车
for(j=1; j<=w; j++) board[i][j]=getchar();
}
//将最下边和最右边两条边初始化为空,之前初始化过的格子跳过
for(i=0; i<=w; i++)
board[h+1][i+1] = ' ';
for(i=0; i<=h; i++)
board[i+1][w+1] = ' ';
int begin_x,begin_y,end_x,end_y,count=0;
/*for(i=0; i<MAXIN+2; i++){
for(j=0; j<MAXIN+2; j++){
printf("%c", board[i][j]);
}
printf("\n");
}*/
while(scanf("%d %d %d %d",&begin_x,&begin_y,&end_x,&end_y)
&& begin_x>0){ //读入起始点和终点
count++;
minstep = 100000; //初始化成一个很大的数
memset(mark, false, sizeof(mark)); //将mark数组全部初始化成false
//递归搜索
Search(begin_x, begin_y, end_x, end_y, 0, -1);
//输出结果
if(minstep<100000) printf("Pair %d: %d segments.\n",count, minstep);
else printf("Pair %d:impossible.\n", count);
getchar();
}
printf("\n");
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的算法题--小游戏全部内容,希望文章能够帮你解决算法题--小游戏所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。