- 浏览: 70393 次
- 性别:
- 来自: 杭州
最新评论
题目见zoj 1091
使用宽度搜索优先来求解,这个算法已经忘记的差不多了,所以写出来的代码很罗嗦,看起来很不清晰。
好像还可以直接用公式或者神经网络算法求解,详见Knight's Tour
/* zoj 1091 Knight Moves */ #include <stdio.h> #include <string.h> #define MAX 100 #define BOARDSIZE (8+1) struct queueStruct{ int x; int y; int step; }queue[MAX],tempQueue; int front; int rear; int minStep; int isVisited[BOARDSIZE][BOARDSIZE]; const int searchTable[8][2] = {{-2,-1},{-1,-2},{-2,1},{-1,2},{1,2},{2,1},{1,-2},{2,-1}}; int bfs(int startx, int starty, int endx, int endy, int step); int main(void) { char src[3],des[3]; int startx, starty, endx, endy; while(scanf("%s %s",src,des) == 2) { memset(isVisited,0,sizeof(isVisited)); memset(queue,0,sizeof(queue)); front = rear = 0; startx = src[0] - 'a' + 1; starty = src[1] - '0'; endx = des[0] - 'a' + 1; endy = des[1] - '0'; bfs(startx,starty,endx,endy,0); printf("To get from %s to %s takes %d knight moves.\n",src,des,minStep); } return 0; } int bfs(int startx, int starty, int endx, int endy, int step) { int i; struct queueStruct q; if(startx == endx && starty == endy) { minStep = step; return 0; } isVisited[startx][starty] = 1; tempQueue.x = startx; tempQueue.y = starty; tempQueue.step = step; queue[rear++] = tempQueue; while(front < rear) { tempQueue = queue[front++]; for(i = 0; i < BOARDSIZE; i++) { /* q = tempQueue;*/ q.x = tempQueue.x + searchTable[i][0]; q.y = tempQueue.y + searchTable[i][1]; q.step = tempQueue.step + 1; if(q.x < 1 || q.x > 8 || q.y < 1 || q.y > 8 ||isVisited[q.x][q.y]) continue; if(q.x == endx && q.y == endy) { minStep = q.step; return 0; } queue[rear++] = q; isVisited[q.x][q.y] = 1; } } return 0; }
发表评论
-
最小c编译器
2011-11-08 14:09 1420最小c编译器(来源 (最好在linux下操作))代码有好几个 ... -
the development of c language(转)
2011-11-08 09:25 1094c语言之父Dennis Ritchie 写的关于c语言开发历 ... -
C语言,你真的弄懂了么?
2011-11-07 12:42 1723程序(来源 ): #include <stdi ... -
pe文件格式实例解析
2011-11-07 10:05 0环境:windows xp 速龙3000+(即x86兼容32位 ... -
小型elf "Hello,World"程序
2011-11-06 23:59 1320参考链接:http://timelessname.com/el ... -
elf文件格式实例解析
2011-11-05 23:00 6277试验环境:archlinux 速龙3000+(即x86兼 ... -
高质量的c源代码
2011-11-03 10:18 1091现在自由软件及开源软件越来越流行,有大量的附带源程序 ... -
fltk 库
2011-09-26 19:47 1770fltk是一个小型、开源、支持OpenGL 、跨平台(win ... -
《Introduction to Computing Systems: From bits and gates to C and beyond》
2011-09-25 23:33 2115很好的一本计算机的入门书,被很多学校采纳作为教材,作者Yale ... -
csapp bufbomb实验
2011-09-16 14:21 4543csapp (《深入理解计算机系统》)一书中有一个关于缓冲区 ... -
the blocks problem(uva 101 or poj 1208)
2011-09-11 20:57 1802题目描述见:uva 101 or poj 1208 ... -
the blocks problem(uva 101 or poj 1208)
2011-09-11 20:56 0题目描述见:uva 101 or poj 1208 ... -
部分排序算法c语言实现
2011-09-02 14:51 988代码比较粗糙,主要是用于对排序算法的理解,因而忽略了边界和容错 ... -
编译器开发相关资源
2011-08-31 08:40 1167开发编译器相关的一些网络资源: how difficu ... -
zoj 1025 Wooden Sticks
2011-07-23 20:25 940题目见:zoj 1025 先对木棒按照长度进行排序,然后再计 ... -
zoj 1088 System Overload
2011-07-23 17:30 1138约瑟夫环 (josephus problem )问题, ... -
zoj 1078 palindrom numbers
2011-07-22 19:31 1119题目见zoj 1078 主要是判断一个整数在基数为2 ... -
zoj 1006 do the untwist
2011-07-22 13:24 900题目见zoj 1006 或poj 1317 简单 ... -
zoj 3488 conic section
2011-07-22 12:23 965题目见zoj 3488 很简单的题目,却没能一次搞定,因 ... -
zoj 1005 jugs
2011-07-22 11:43 806题目内容见zoj1005 由于A,B互素且A的容 ...
相关推荐
能AC 通过的c++代码,包括zoj1002,1091,1789
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
zoj吐血制作,希望大家喜欢
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
zoj 1002 C语言的为什么描述要这么多字啊。。