Day2-I-Knight's Problem POJ - 3985
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).
Input
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).
Output
Sample Input
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
Sample Output
3
IMPOSSIBLE 简述:给你起点和终点以及m种移动方式,问是否能够达到终点,若能输出最短步数。
分析:这题乍一看是一道简单的BFS,但是他没有限制搜索“棋盘”的大小,直接裸会T,那么我们就要进行合理剪枝,去除一些不可能的情况。
1.若该点是背离起点/终点的,应剪枝:
这点应该比较好理解,背离的路径一定不会是最短路径,用余弦定理即可判断。
但是,如果最短路径是要先背离再回来呢?我们先引入一个结论:改变路径的顺序不会影响最终到达终点,以图为例:
这样,就引出了我们的第二种剪枝:
2.每一步必须在最大距离之内:
既然可以随意转换步数,那么我们就可以将每一步限制在最大距离之内,这样就可以将无穷距离进行限制,转换为有限的,并且也能将第一种剪枝无法判断的情况(未背离但是不会达到)給剪掉。
PS:计算距离的时候用的是点到直线的距离公式(梦回高中
这题还有一点,要手写一下hash,用STL的会T,参考黑书(数据结构与算法分析)上的分离链接法。
(有看不懂的欢迎留言,文学功底有限。。)
代码如下:
#define sqr(x) ((x) * (x))
const int prime = ; int T, sx, sy, ex, ey, n, order[][], head[prime], idx, length;
double A, B, C, d; // Ax+By+C=0 struct Node {
int x, y, step;
}; struct unit {
int x, y, next;
} edge[]; int Hash(int x,int y) {
return (((x << ) ^ y) % prime + prime) % prime; // 防止负数
} bool addedge(int key,int x,int y) {
for (int i = head[key]; i != -; 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;
} bool check(int x,int y) {
int t1 = sqr(x - sx) + sqr(y - sy);
int t2 = sqr(ex - x) + sqr(ey - y);
double t3 = sqr(A * x + B * y + C) * 1.0 / ((sqr(A) + sqr(B)) * 1.0);
if(t2 > t1 + length || t1 > t2 + length) // 情况1
return false;
if(t3 <= d)
return true; // 情况2
return false;
} bool bfs() {
queue<Node> q;
Node p, tmp;
p.x = sx, p.y = sy, p.step = ;
q.push(p);
addedge(Hash(sx, sy), sx, sy);
while(!q.empty()) {
p = q.front(), q.pop();
if(p.x == ex && p.y == ey) {
printf("%d\n", p.step);
return true;
}
for (int i = ; i < n; ++i) {
tmp = p;
tmp.x += order[i][], tmp.y += order[i][];
if(check(tmp.x,tmp.y)&&addedge(Hash(tmp.x,tmp.y),tmp.x,tmp.y)) {
tmp.step++;
q.push(tmp);
}
}
}
return false;
} int main() {
scanf("%d", &T);
while(T--) {
d = , idx = ;
scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
scanf("%d", &n);
for (int i = ; i < n; ++i) {
scanf("%d%d", &order[i][], &order[i][]);
d = max(d, sqr(order[i][]) + sqr(order[i][])*1.0);
}
A = ey - sy, B = sx - ex, C = ex * sy - ey * sx;
length = sqr(ex - sy) + sqr(ey - sy);
memset(head, -, sizeof(head));
if(!bfs())
printf("IMPOSSIBLE\n");
}
return ;
}
最新文章
- Bringing Whoops Back to Laravel 5
- angularjs中的directive scope配置
- HiKariCP的数据源配置
- 微信开发中网页授权access_token与基础支持的access_token异同
- 夺命雷公狗-----React---25--小案例之react经典案例todos(单选框的修改)
- java.lang.ClassNotFoundException: net.sf.json.JSONArray,java.lang.NoClassDefFoundError: net/sf/json/JSONArray jetty跑项目遇到的问题
- spring中使用mockito
- wp7 BaseDictionary<;TKey, TValue>;
- sql 中实现打乱数据的排序
- Navigation Bar上的返回按钮文本颜色,箭头颜色以及导航栏按钮的颜色
- 【解决】小米M1刷机教程(卡刷)
- IOS中获取各种文件的目录路径的方法-备
- openstack controller ha测试环境搭建记录(十二)——配置neutron(计算节点)
- 如何简单的实现新手引导之UGUI篇
- 一:Spring Boot、Spring Cloud
- 分享Sql Server 2008 r2 数据备份,同步服务器数据(一.本地备份)
- Mac效率:配置Alfred web search
- Javascript reduce方法
- Luogu P4011 孤岛营救问题
- 这里有一篇简单易懂的webSocket 快到碗里来~