文档章节

跳马问题

日拱一卒
 日拱一卒
发布于 2014/05/29 18:39
字数 583
阅读 37
收藏 0
问题:

半张象棋棋盘,一马从左下角跳到右上角,只能往右跳,不能往左跳,输出所有跳步步骤。


算法1:逆向递归
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
	int x, y;
	struct node *nextStep;
}stepNode;

stepNode *q;
stepNode* arrProcess[100];
int count = 0;

int func(int, int, stepNode*);

void main(){
	int destX, destY;
	int i, flag;
	stepNode *p;

	printf("请输入要到达点的坐标(0<x<9, 0<y<5):");
	scanf("%d%d", &destX, &destY);
	flag = func(destX, destY, NULL);
	if(flag == 0){
		printf("亲,跳不到点(%d,%d)哟!\n", destX, destY);
	}else{
		printf("共有%d种走法\n", count);
		for(i=0; i<count; i++){
			printf("第%d中方法:\n", i+1);
			for(p=arrProcess[i]; p!=NULL; p=p->nextStep) printf("(%d,%d)\t", p->x, p->y);
			printf("\n");
		}
	}
}

int func(int x, int y, stepNode *p){
	
	int flag1, flag2, flag3, flag4;

	if(x<0 || x>8 || y<0 || y>4) return 0;

	q = (stepNode*)malloc(sizeof(stepNode));
	q->x = x;
	q->y = y;
	q->nextStep = p;
	p = q;
	
	if(x==0 && y==0){
		arrProcess[count++] = q;
		return 1;
	}

	flag1 = func(x-1, y-2, p);
	flag2 = func(x-2, y-1, p);
	flag3 = func(x-2, y+1, p);
	flag4 = func(x-1, y+2, p);
	if(flag1+flag2+flag3+flag4 == 0){
		free(p);
		return 0;
	}else{
		return 1;
	}
}


算法2:正向递归
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
	int x, y;
	struct node *p1, *p2, *p3, *p4;
	int n1, n2, n3, n4;
}stepNode;

int destX, destY, count;
stepNode *head;

int func(int, int, stepNode **);
void showProcess();

void main(){
	printf("请输入要到达点的坐标(0<x<9, 0<y<5):");
	scanf("%d%d", &destX, &destY);
	count = func(0, 0, &head);
	showProcess();
}

int func(int x, int y, stepNode **p){
	int n;

	*p = (stepNode *)malloc(sizeof(stepNode));
	(*p)->x = x; (*p)->y = y;
	if(x<0 || x>8 || y<0 || y>4 || x>destX){
		n=0;
	}else if(x==destX && y==destY){
		(*p)->p1 = NULL;
		(*p)->p2 = NULL;
		(*p)->p3 = NULL;
		(*p)->p4 = NULL;
		n = 1;
	}else{
		(*p)->n1 = func(x+1, y+2, &((*p)->p1));
		(*p)->n2 = func(x+2, y+1, &((*p)->p2));
		(*p)->n3 = func(x+2, y-1, &((*p)->p3));
		(*p)->n4 = func(x+1, y-2, &((*p)->p4));
		n = (*p)->n1 + (*p)->n2 +  (*p)->n3 + (*p)->n4;
	}
	if(n==0){free (*p); *p = NULL;}
	return n;
}

void showProcess(){
	int i;
	stepNode *p;
	if(count == 0){
		printf("亲,跳不到点(%d,%d)哟!\n", destX, destY);
		return;
	}
	
	printf("共有%d种走法\n", count);
	for(i=0; i<count; i++){
		printf("第%d中走法:\n", i+1);
		p = head;
		while(p!=NULL){
			printf("(%d,%d)  ", p->x, p->y);
			if(p->n1 != 0){p->n1-=1; p=p->p1;}
			else if(p->n2 != 0){p->n2-=1; p=p->p2;}
			else if(p->n3 != 0){p->n3-=1; p=p->p3;}
			else {p=p->p4; p->n4-=1;} 
		}
		printf("\n");
	}
}

调试环境:VC++6.0

© 著作权归作者所有

共有 人打赏支持
日拱一卒
粉丝 16
博文 63
码字总数 24558
作品 0
沈阳
其他
私信 提问
学以致用——Java源码——骑士之旅(跳马)小游戏_优化算法加汇总分析版(Knight’s Tour - Heuristic plus statistics version)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/hpdlzu80100/article/details/85334413 接上一篇,学以致用——Java源码——骑士之旅(跳马)小游戏_优化算法...

预见未来to50
2018/12/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

没有更多内容

Java生成二维码图片

maven配置jar包 <dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.3.3</version></dependency><dependency><groupId>com.google.z......

骑羊放狼灬
7分钟前
2
0
oracle 修改字段类型

1.varchar2 类型修改 例子:alter table T_Node modify (NODE_CONTEXT varchar2(4000)); 2.varchar2 修改为clob 例子: alter table T_Node add hehe clob; update T_Node set hehe=NODE_CO......

qimh
10分钟前
2
0
别再写 bug 了,避免空指针的 5 个案例!

空指针是我们 Java 开发人员经常遇到的一个基本异常,这是一个极其普遍但似乎又无法根治的问题。 本文,栈长将带你了解什么是空指针,还有如何有效的避免空指针。 什么是空指针? 当一个变量...

Java技术栈
14分钟前
5
0
FastJson对BigDecimal保留两位小数(valueFilter)

实现ValueFilter public class BigDecimalValueFilter implements ValueFilter { @Override public Object process(Object o, String name, Object value) {//o是待转换的对象,n......

石日天
16分钟前
1
0
android 颜色透明度参照比

##透明度参照表: 00%=FF(不透明) 5%=F2 10%=E5 15%=D8 20%=CC 25%=BF 30%=B2 35%=A5 40%=99 45%=8c 50%=7F 55%=72 60%=66 65%=59 70%=4c 75%=3F 80%=33 85%=21 90%=19 95%=0c 100%=00(全透......

东街小霸王
17分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部