下次自动登录
现在的位置:
& 综合 & 正文
Knight Moves
骑士游历问题的纯数学方法！！！
下面稍微翻译一下：
描述：给你一个8*8的棋盘,骑士的开始位置,结束位置,让你求得骑士从开始位置开始揍到结束位置需要最小的步数是多少？（注意,骑士走日字）
输入：输入包含多组数据，每一行都是一组开始位置和结束位置,位置由两个字符组成,一个是小写字母(a-h),一个是数字(1-8),起始位置结束位置由一个空格隔开.
输出：输出从起始位置到结束位置,骑士所要走过的最小的步数.按照样例的格式来。
输入样例：
输出样例：
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
-------------------------------------------------------------------------------------------------------------
一般网上见到的都是dp或者bfs方法。。
但是，对于n稍微大一点，比如80*80,100*100的方格，就很麻烦了。
今天中午 ，我终于想出来了一个数学方法。。
是这样的：
首先，对于两个点，只用考虑其横纵坐标的差值。比如a3,a4，横坐标差值为0，纵坐标差值为1
现在设横纵坐标的差值分别是x,y
由于马只能有8种方法，实际上只会出现4种（举个例子，本来方向向量有(1,2),(2,1),(1,-2),(2,-1),(-1,2),(-2,1),(-1,-2),(-2,-1)，但是如果要最小的次数，就不可能同时出现(1,2)和(-1,-2)，依次类推）
所以，我们设方向向量为(1,2),(2,1),(2,-1),(1,-2)的分别有a,b,c,d次，其中a,b,c,d可以为负数，a为负数代表方向向量为(-1,-2)
于是，可以列两个方程：
a+2b+2c+d=x
2a+b-c-2d=y
我们要求的是|a|+|b|+|c|+|d|的最小值
首先把a,b,看做常量，解得
c=(-4a-5b+2x+y)/3
d=(5a+4b-x-2y)/3
那么有a+2b和2x+y模3同余
现在2x+y已知，对于b进行枚举，由于-n/2&=b&=n/2，进行枚举，对每个知道a模3是多少，进而再对可能的a进行枚举，从而解出c,d，进而求出总步数。
但是，特别要注意一点，就是角落的问题。
比如a1,b2按上面方法算的是2，实际是4.
经过计算知，对于8*8的只有4种情况：a1 b2;a8 b7;g2 h1;g7 h8;
对这四种情况单独拿出来说就好了。。
以上就是求解的数学方法。下面贴，对于原来的8*8题目的。
在poj2243上AC了，228K，32MS。
n*n的稍作修改即可。
--------------------------------
#include &iostream&
#include &string&
int f(int a)
//就是abs(a)，绝对值
return 0-a;
int main()
string s1,s2;
int a,b,c,d,x,y,s,m;
while (cin && s1 && s2)
if ((s1=="a1" && s2=="b2") || (s1=="b2" && s2=="a1") || (s1=="g2" && s2=="h1") || (s1=="h1" && s2=="g2"))
cout && "To get from " && s1 && " to " && s2 && " takes 4 knight moves." &&
if ((s1=="a8" && s2=="b7") || (s1=="b7" && s2=="a8") || (s1=="g7" && s2=="h8") || (s1=="h8" && s2=="g7"))
cout && "To get from " && s1 && " to " && s2 && " takes 4 knight moves." &&
x=s2[0]-s1[0];
//横坐标差值
y=s2[1]-s1[1];
//纵坐标差值
for (b=-4;b&=4;b++)
m=y+2*x-2*b+30;
//a模3的余数
for (a=m-6;a&=m+6;a+=3)
c=(2*x+y-4*a-5*b)/3;
//求出c和d
d=(5*a+4*b-x-2*y)/3;
if (s&f(a)+f(b)+f(c)+f(d))
s=f(a)+f(b)+f(c)+f(d);
//判断是否是最小的
cout && "To get from " && s1 && " to " && s2 && " takes " && s && " knight moves." &&
&&&&推荐文章:
【上篇】【下篇】poj 2418 trie树统计单词出现的个数 - The time is passing - ITeye技术网站
博客分类：
一 题意：输入很多棵树(单词)，统计每种树所占的百分比
二 算法：用trie树轻松解决，trie树的典型应用就是统计单词出现的个数。
三 代码如下，ps：清华大学《数据结构-C语言版》的trie树实现很傻逼，我不知道它如何
解决前缀字符串的问题，比如统计aaa和aaabb的出现次数
#include &stdio.h&
#include &string.h&
#include &stdlib.h&
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#define debug(...)
struct trie_node {
struct trie_node
*child[256]; /* 分支节点的孩子指针 */
/* 用于记录单词出现的次数，若count大于0，说明
从根节点到此节点的父节点构成了一个单词，这个
单词的次数就是count */
/* 树的总数 */
struct trie_node *init_trie_tree()
return (struct trie_node *)calloc(1, sizeof(struct trie_node));
void insert(struct trie_node *root, char *word)
struct trie_node
debug("%s.......\n", word);
for (p = *p; p++) {
debug("开始插入%c\n", *p);
if (node-&child[*p] == 0) {
debug("%c不存在,创建新节点\n", *p);
node-&child[*p] = (struct trie_node *)calloc(1, sizeof(struct trie_node));
debug("%c存在\n", *p);
node = node-&child[*p];
//到达记录统计单词次数的节点
node-&count++;
debug("%s有%d个\n\n", word, node-&count);
/* 借助pos指针来遍历每个单词，初始时pos指向worddump的第一个位置
* 若往孩子节点走，则pos后移，若往兄弟节点走，则pos保持不动
void dfs_travel(struct trie_node *root)
static char
worddump[31];
static int
if (root-&count) { /* 如果count不为0，则肯定找到了一个单词 */
worddump[pos] = '\0';
if (worddump[0]) {
printf("%s %0.4f\n", worddump, ((float)root-&count*100)/(float)n);
for (i = 0; i & 256; i++) {
if (root-&child[i]) {
debug("找到%c\n", i);
worddump[pos++] =
/* 往下遍历，pos跟着后移，供孩子节点使用 */
dfs_travel(root-&child[i]);
pos--; /* 恢复位置,供下一个兄弟节点使用 */
debug("回退1个位置\n");
int main()
struct trie_node
root = init_trie_tree();
while (gets(line)) {
insert(root, line);
dfs_travel(root);
浏览: 427201 次
来自: 北京
写的不错，很透彻
好，赞扬！
赞一个~！ ，现在正在看redis 所以接触到跳表
vote--后还要判断是否为0吧，如果为0则废掉重新置位can ...
树状数组不是求前缀和的吗？那那个detial数组是怎么回事啊博客访问： 311195
博文数量： 121
博客积分： 3195
博客等级： 中校
技术积分： 1195
注册时间：
APP发帖 享双倍积分
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
Memory: 224K
Time: 16MS
(x+m*t) - (y+n*t) = p *& (tllab)
(n-m) * t + ll * p = x –
a = n-m, &b = ll,& c = gcd(a, b), &d = x-y;
a * t + b * p =&& (1)
t0 ,p0, c = gcd(a, b);
a * t0 + b * p0 = &(2)
c = gcd(a, b),
a * t / cb * t / c
&(2)(d / c)
a * t0 *(d / c) + b * p0 * (d / c) =
&t0 * (d / c)
a * ( t0 *(d / c) + b*n) + b * (p0 * (d / c) – a*n) = (n)
(t0 * (d / c) % b + b) %
&&& 0a, b.& gcd(a, b)a, b x y gcd(a, b) = a * x + b *
b = 0 gcd(a, b) = a ,
x = 1, y = 0;
& a * x + b * y = gcd(a, b);&& (1)
&&& b * x0 + (a % b) * y0 = gcd( b, a % b);&& (2)
; gcd(a, b) = gcd (b, a % b);
(1)(2) &a * x + b * y = b * x0 + (a % b) * y0
&&&&&&&&&&&&&&&&&&&& = b * x0 + (a – a / b * b) * y0 &&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&& = a * y0 + ( x0 – a / b * y0 ) * b
x = y0, y = x0 – a / b * y0;
void extend_euild(int a, int b){&&&&if(b == 0)&&&&{&&&&&&&&t = 1;&&&&&&&&p = 0;&&&&&&&&c = a;&&&&}&&&&else {&&&&&&&&extend_euild(b, a%b);&&&&&&&&int temp = t;&&&&&&&&t = p;&&&&&&&&p = temp - a/b*p;&&&&}}
#include <iostream>using namespace std;long long t, p, c;void extend_euild(int a, int b){&&&&if(b == 0)&&&&{&&&&&&&&t = 1;&&&&&&&&p = 0;&&&&&&&&c = a;&&&&}&&&&else&&&&{&&&&&&&&extend_euild(b, a%b);&&&&&&&&int temp = t;&&&&&&&&t = p;&&&&&&&&p = temp - a/b*p;&&&&}}int main(){&&&&int i, j, ok = 0, d, a, b;&&&&long long x, y, m, n, l;&&&&freopen("in.txt", "r", stdin);&&&&cin >> x >> y >> m >> n >> l;&&&&&&&&if(n == m)&&&&&&&&ok = 1;&&&&else{&&&&&&&&a = n-m;&&&&&&&&d = x-y;&&&&&&&&b = l;&&&&&&&&extend_euild(a, b);&&&&&&&&if(d % c !=0)&&&&&&&&&&&&ok = 1;&&&&}&&&&if(ok)&&&&&&&&cout << "Impossible" << endl;&&&&else&&&&{&&&&&&&&b = b / c;&&&&&&&&d = d / c;&&&&&&&&long long v = d * t;&&&&&&&&cout << (v%b+b)%b << endl;&&&&}&&&&getch();&&&&return 0;}
阅读(8534) | 评论(1) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
看了多少了，对我这样的新手来说还是你分析的透彻。感激不尽啊。
请登录后评论。JAVASCRIPT:}