首页 > ACM题库 > HDU-杭电 > HDU 3766-Knight’s Trip-BFS-[解题报告]HOJ
2015
04-10

HDU 3766-Knight’s Trip-BFS-[解题报告]HOJ

Knight’s Trip

问题描述 :

In chess, each move of a knight consists of moving by two squares horizontally and one square vertically, or by one square horizontally and two squares vertically. A knight making one move from location (0,0) of an infinite chess board would end up at one of the following eight locations: (1,2), (-1,2), (1,-2), (-1,-2), (2,1), (-2,1), (2,-1), (-2,-1).

Starting from location (0,0), what is the minimum number of moves required for a knight to get to some other arbitrary location (x,y)?

输入:

Each line of input contains two integers x and y, each with absolute value at most one billion. The integers designate a location (x,y) on the infinite chess board. The final line contains the word END.

输出:

Each line of input contains two integers x and y, each with absolute value at most one billion. The integers designate a location (x,y) on the infinite chess board. The final line contains the word END.

样例输入:

1 2
2 4
END

样例输出:

1
2

最近练习BFS,看某位大神博客的小结跟着做来着,然后碰到这个…就是跳马的问题.没给出棋盘,就是说没有范围,n,m可以很大,用BFS数据大一点看着很慢,感觉肯定是过不了,大神博客写着:之前需要逼近下,然后再搜索,或者直接枚举判断下就行了。…俩都不会,无法,看看怎么逼近,尝试一小时还是不会。找个数学大神看看有啥规律可循没有。推出来公式之后一直WA….拿着原先的搜索对照测试结果一样不理解…万万没想到啊万万没想到,卧槽换了一种输入方式就AC了…心中万只草泥马奔腾而过啊,一晚上的时间啊
全部浪费这个题了…

题目几个比较坑的地方:范围真的很大,最起码32M内存你开不起。跳马可以跳到坐标是负的地方- -只能说卧槽.还有就是有几个点要单独处理。附上代码:

#include<stdio.h>
#include<string.h>
int main()
{
    char c[20];
    while(scanf("%s",c),c[0]!='E')
    {
        int x=0,y,flag=1;
        int k;
		for(int i=0;c[i];i++)
		{
			if(c[i]=='-'&&i==0)
				flag=-1;
			else
            x=x*10+c[i]-48;
		}
		x=x*flag;
        scanf("%d",&y);
        if(x<0)
            x=-x;
        if(y<0)
            y=-y;
        if(y<x) {k=x;x=y;y=k;}
        if(y<=2*x)
        {
            if(x==1&&y==1)
                printf("2\n");
            else if(x==2&&y==2)
                printf("4\n");
            else
                printf("%d\n",(x+y)/3+(x+y)%3);
        }
        else
        {
            int ans=x;
            int c=(y-2*x)%4;
            ans+=c;
            ans+=(y-2*x-c)/2;
            if(y==1&&x==0)
                ans=3;
            printf("%d\n",ans);
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/azx736420641/article/details/38516409


,
  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  4. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示