[算法]穷举寻径。。。
中国象棋棋盘上，从指定的起始位置，到达指定的位置，马有哪几条路径。初略写了算法描述，就去听单片机讲座了，想想那个算法有考虑不周的地方。。。
试卷上说的好像是从左上角到右下角 的一个特例，
上面的题目是刚在研发中心的论坛上发现的
[ 本帖最后由 iptton 于 2006-10-21 21:50 编辑 ] 核心算法没写上，先帖了。。。
#include <stdio.h>
typedef struct point{
int x;
int y;
int flag;
}T_chess;
struct pointStack{
struct point * value;
struct pointStack *next;
}
T_chess chess;
void findDir(struct point*,struct point*);
void printDir(struct point*);
struct pointStack * allocStack(struct point* value);
int main(){
struct point start,end;
//initial data
for(i=0;i<9;i++){
for(j=0;j<10;j++){
chess.x=i;
chess.y=j;
chess.flag=0;
}
}
scanf("%d %d %d %d",&start.x,&start.y,&end.x,&end.y);
start.flag=1;
end.flag=0;
findDir(&start,&end);
}
void findDir(struct point *s,struct point *e)
{
}
void printDir(struct pointStack *s)
{
struct pointStack *tmp;
while(!s){
printf("[%d,%d]",(s->value).x,(s->value).y);
tmp=s->next;
s=tmp;
}
}
struct pointStack * allocStack(struct point * value){
struct pointStack *ret=malloc(sizof(struct pointStack));
ret->next=null;
ret->value=s;
return ret;
}
[ 本帖最后由 iptton 于 2006-10-21 19:47 编辑 ] lz能不能简单介绍一下这个算法啊,我看到这道题是,根本不知从什么方向着手... 楼上可以去找找 寻径算法
搜索这两个关键词：
深度优先 回溯
算法的计算机实现是要依赖相应的数据结构的，
不过学C语言时已学过链表了，所以这道题应该只是考算法设计
说说我的思路：
每走一步之前，
1
找到下一步可以走的所有的位置，
标记之（如图中点红色，本来应该各个点的“红”色都不同才对的。。。），
选择上面标记 红 了的步中一步
标记此步为已经走过了（如图中的黑色），以免在同两步上死循环
2
。。。。。。（有空再写）
计算机对每一个点（棋位）的信息存储应当包括：X，Y座标，当前路径是否已走过这一步的标记（flag）,如果这一步走完了,以这一步为起点可走的(即FLAG为false的)点的位置组（为节省空间，可用链表），所以一个点的数据结构应该为：
typedef struct point{
int x; // [0,9)
int y; // [0,10)
int flag; //0 OR 1
struct point*next;
}T_point; //因为中国象棋只有 10＊9
为保存以走的路径信息，又需要一个组有顺序，按先进后出规则操作的的空间（一般称这个为栈）：
struct curPath{
struct point *pointInPath; //为节省空间，用指针，初始化时要记得用NULL
struct curPath* next; //
}
[ 本帖最后由 iptton 于 2006-10-22 12:42 编辑 ] 很明显，第二次回溯后的线路是不能到达目的点的（这个因应该是这个问题的解的优化之处） IP，这个可能对你有帮助。
较高人工智能的人机博弈程序实现(多个算法结合)含C++源码 这道题只是一道很简单的算法题。。。
离AI还远着呢。。。。
页:
[1]