文档章节

跳马问题

日拱一卒
 日拱一卒
发布于 2014/05/29 18:39
字数 583
阅读 33
收藏 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

© 著作权归作者所有

共有 人打赏支持
日拱一卒
粉丝 15
博文 63
码字总数 24558
作品 0
沈阳
其他

暂无文章

arts-week5

Algorithm 824. Goat Latin - LeetCode 152. Maximum Product Subarray - LeetCode 110. Balanced Binary Tree - LeetCode 67. Two Sum II - Input array is sorted - LeetCode 665. Non-dec......

yysue
11分钟前
0
0
iOS开发之AddressBook框架详解

iOS开发之AddressBook框架详解 一、写在前面 首先,AddressBook框架是一个已经过时的框架,iOS9之后官方提供了Contacts框架来进行用户通讯录相关操作。尽管如此,AddressBook框架依然是一个非...

珲少
40分钟前
1
0
两年摸爬滚打 Spring Boot,总结了这 16 条最佳实践

Spring Boot是最流行的用于开发微服务的Java框架。在本文中,我将与你分享自2016年以来我在专业开发中使用Spring Boot所采用的最佳实践。这些内容是基于我的个人经验和一些熟知的Spring Boot...

Java填坑之路
今天
3
0
《Spring5学习》04 - 面向切面编程

一、Spring面向切面编程的基本概念 面向切面编程(即AOP):把项目中需要再多处使用的功能比如日志、安全和事务等集中到一个类中处理,而不用在每个需要用到该功能的地方显式调用。 横切关注...

老韭菜
今天
2
0
day61-20180819-流利阅读笔记

跑道没了,它们还在跑:澳门赛狗业的遗孤 Daniel 2018-08-19 1.今日导读 相信你早就知道香港有个赛马会,可是你听说过香港的邻居澳门原本有个赛狗会吗?其实,对于澳门人来说,赛狗这项活动历...

aibinxiao
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部