首页 > ACM题库 > HDU-杭电 > HDU 3690-Knight’s Problem[解题报告]HOJ
2014
11-30

HDU 3690-Knight’s Problem[解题报告]HOJ

Knight’s Problem

问题描述 :

You must have heard of the Knight’s Tour problem. In that problem, a knight is placed on an empty chess board and you are to determine whether it can visit each square on the board exactly once.

Let’s consider a variation of the knight’s tour problem. In this problem, a knight is place on an infinite plane and it’s restricted to make certain moves. For example, it may be placed at (0, 0) and can make two kinds of moves: Denote its current place as (x,y), it can only move to (x+1,y+2) or (x+2,y+1). The goal of this problem is to make the knight reach a destination position as quickly as possible (i.e. make as less moves as possible).

输入:

The first line contains an integer T ( T < 20) indicating the number of test cases.

Each test case begins with a line containing four integer: fx fy tx ty(-5000<=fx,fy,tx,ty<=5000). The knight is originally placed at (fx, fy) and (tx, ty) is its destination.

The following line contains an integer m(0<m<=10), indicating how many kinds of moves the knight can make.

Each of the following m lines contains two integer mx my(-10<=mx,my<=10; |mx|+|my|>0), which means that if a knight stands at (x,y), it can move to (x+mx,y+my).

输出:

The first line contains an integer T ( T < 20) indicating the number of test cases.

Each test case begins with a line containing four integer: fx fy tx ty(-5000<=fx,fy,tx,ty<=5000). The knight is originally placed at (fx, fy) and (tx, ty) is its destination.

The following line contains an integer m(0<m<=10), indicating how many kinds of moves the knight can make.

Each of the following m lines contains two integer mx my(-10<=mx,my<=10; |mx|+|my|>0), which means that if a knight stands at (x,y), it can move to (x+mx,y+my).

样例输入:

2
0 0 6 6
5
1 2
2 1
2 2
1 3
3 1
0 0 5 5
2
1 2
2 1

样例输出:

3
IMPOSSIBLE

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <queue>
#include <set>
#include <utility>
#define MAX(a , b) ((a) > (b) ? (a) : (b))
#define sqr(x) ((x) * (x))
#define mp make_pair
typedef long long ll;
using namespace std;
const int maxn = 12;
const int maxm = 400000;
const int kr = 1;
const int prime = 999997;
struct ddd
{
    int x,y;
    int step;
};
struct node
{
    int x,y;
    int next;
}edge[maxm];
int head[prime],vec[maxn][2];
queue <ddd> Q;
int sx,sy,tx,ty,a,b,c,d,n,idx;

void init()
{
    memset(head,-1,sizeof(head));
    idx = 0;
    return;
}

int hash(int x,int y)
{
    return (((x << 15) ^ y) % prime + prime) % prime;
}

bool addedge(int key,int x,int y)
{
    for(int i=head[key];i != -1;i=edge[i].next)
    {
        if(edge[i].x == x && edge[i].y == y) return false;
    }
    edge[idx].x = x;
    edge[idx].y = y;
    edge[idx].next = head[key];
    head[key] = idx++;
    return true;
}

void read()
{
    d = 0;
    scanf("%d %d %d %d",&sx,&sy,&tx,&ty);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&vec[i][0],&vec[i][1]);
        d = MAX(d , sqr(vec[i][0]) + sqr(vec[i][1]));
    }
    a = ty - sy;
    b = sx - tx;
    c = sy * tx - sx * ty;
    return;
}

bool IsValid(int x,int y)
{
    if(sqr(x - sx) + sqr(y - sy) <= sqr(kr) * d) return true;
    if(sqr(x - tx) + sqr(y - ty) <= sqr(kr) * d) return true;
    if((tx - sx) * (x - sx) + (ty - sy) * (y - sy) < 0) return false;
    if((sx - tx) * (x - tx) + (sy - ty) * (y - ty) < 0) return false;
    if(sqr(ll(a) * x + b * y + c) <= ll(d) * (sqr(a) + sqr(b))) return true;
    return false;
}

void bfs()
{
    while(!Q.empty()) Q.pop();
    ddd cur,tmp;
    tmp.x = sx;
    tmp.y = sy;
    tmp.step = 0;
    Q.push(tmp);
    addedge(hash(sx , sy) , sx , sy);
    while(!Q.empty())
    {
        cur = Q.front();
        Q.pop();
        if(cur.x == tx && cur.y == ty)
        {
            printf("%d\n",cur.step);
            return;
        }
        for(int i=0;i<n;i++)
        {
            int xx = cur.x + vec[i][0];
            int yy = cur.y + vec[i][1];
            if(IsValid(xx , yy) && addedge(hash(xx , yy) , xx , yy))
            {
                tmp.x = xx;
                tmp.y = yy;
                tmp.step = cur.step + 1;
                Q.push(tmp);
            }
        }
    }
    puts("IMPOSSIBLE");
    return;
}

int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        init();
        read();
        bfs();
    }
    return 0;
}

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  5. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。