- 浏览: 583767 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
POJ1696题意:
一只很特殊的蚂蚁,只能向坐转,并且不能经过已经走过的路。一张地图上有n个食物让蚂蚁去采集,求蚂蚁经过所有食物的顺序(找出一条最长的非右拐的路径)。
样例:
Sample Input
2 (二次测试)
10 (十个食物点)
1 4 5 (点的编号,x坐标,y坐标)
2 9 8
3 5 9
4 1 7
5 3 2
6 6 3
7 10 10
8 8 1
9 2 4
10 7 6
14
1 6 11
2 11 9
3 8 7
4 12 8
5 9 20
6 3 2
7 1 6
8 2 13
9 15 1
10 14 17
11 13 19
12 5 18
13 7 3
14 10 16
Sample Output
10 8 7 3 4 9 5 6 2 1 10
14 9 10 11 5 12 8 7 6 13 4 14 1 3 2
分析:
每次找到一个基准点p0,最开始的时候是最左下角的点,然后我们再从未访问的点中找到相对于p0最小极角的那个点,比较极角用叉积来计算,每次迭代总是用此次循环中找到的最小极角来代替p0,然后再以这个新的p0,找到剩下的点中的最小极角,这样我们找到的就是一条最大的不右转的路径了。
下面是AC过的代码:
源码下载:
一只很特殊的蚂蚁,只能向坐转,并且不能经过已经走过的路。一张地图上有n个食物让蚂蚁去采集,求蚂蚁经过所有食物的顺序(找出一条最长的非右拐的路径)。
样例:
Sample Input
2 (二次测试)
10 (十个食物点)
1 4 5 (点的编号,x坐标,y坐标)
2 9 8
3 5 9
4 1 7
5 3 2
6 6 3
7 10 10
8 8 1
9 2 4
10 7 6
14
1 6 11
2 11 9
3 8 7
4 12 8
5 9 20
6 3 2
7 1 6
8 2 13
9 15 1
10 14 17
11 13 19
12 5 18
13 7 3
14 10 16
Sample Output
10 8 7 3 4 9 5 6 2 1 10
14 9 10 11 5 12 8 7 6 13 4 14 1 3 2
分析:
每次找到一个基准点p0,最开始的时候是最左下角的点,然后我们再从未访问的点中找到相对于p0最小极角的那个点,比较极角用叉积来计算,每次迭代总是用此次循环中找到的最小极角来代替p0,然后再以这个新的p0,找到剩下的点中的最小极角,这样我们找到的就是一条最大的不右转的路径了。
下面是AC过的代码:
import java.util.Scanner; import java.util.Arrays; class point implements Comparable { int id ;//食物原始的编号 int ord ;//蚂蚁经过的顺序 double x;//食物的x坐标 double y;//食物的y坐标 public int compareTo(Object o) {//升序排列 return this.ord - ((point) o).ord; } } public class Main{ point[] p;//所有的食物点 boolean vis[] ;//标记是否被蚂蚁吃过了 int n ;//食物的个数 public Main(){ } //向量(x1,y1),(x2,y2)的叉积 public double det(double x1,double y1,double x2,double y2){ return x1*y2 - x2*y1; } //小于0,说明向量ab的极角大于ac的极角 double cross(point a,point b,point c){ return det(b.x - a.x, b.y - a.y, c.x - a.x,c.y - a.y); } //求距离 double dis(point a,point b) { double x1 = a.x; double y1 = a.y; double x2 = b.x; double y2 = b.y ; return (x2 - x1 )*(x2 - x1) + (y2-y1)*(y2 - y1); } //pre:蚂蚁开始的位置,num:蚂蚁经过的顺序 void dfs(int pre,int num){ if(num == n) return ; int mi = 1; while(vis[mi]) mi++;//找一个没有被蚂蚁吃过的点 //在没有吃完的点中找出极角最小的点 for(int i = mi + 1 ;i <= n;i++){ if(vis[i]) continue ;//再找一个没有被蚂蚁吃过的点 double w = cross(p[pre],p[mi],p[i]);//计算叉积 if(w < 0) mi = i;//记录极角小的那个点,极角相同取距离近的点 if((w ==0) && dis(p[pre],p[i]) < dis(p[pre],p[mi])) mi = i; } p[mi].ord = num + 1;//记录吃的顺序 vis[mi] = true ;//标记为已吃过 dfs(mi,num + 1) ;//递归 } public static void main(String args[]){ Main ma=new Main(); ma.go(); } public void go(){ Scanner in=new Scanner(System.in); int t; t=in.nextInt(); while(t-->0){ n=in.nextInt(); int mi = 1 ; vis=new boolean[n+1]; p=new point[n+1]; p[0]=new point();//这个点无用。 for(int i = 1 ; i<= n;i++){//从命令行输入食物信息 p[i]=new point(); p[i].id=in.nextInt();//食物的编号 p[i].x=in.nextDouble();//x坐标 p[i].y=in.nextDouble(); //y坐标 //找y最小的食物点,也即蚂蚁应该第一个吃的点 if(p[mi].y > p[i].y) mi = i; } vis[mi] = true;//蚂蚁最先吃的食物点 p[mi].ord = 1 ;//蚂蚁经过的顺序为1 dfs(mi,1);//从这点开始深搜 Arrays.sort(p);//全部解决,按蚂蚁经过的顺序排序所有点 System.out.printf("%d",n); for(int i = 1;i <=n;i++){ System.out.printf(" %d",p[i].id) ; } System.out.println(); } } }
源码下载:
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3658题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1526POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2981POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1431POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1848题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1593关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1822关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1807POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1829POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
学习凸包(五):卷包裹算法--兼解POJ1113(JAVA)
2012-12-22 13:57 1525一种形象的理解是 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1563分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(四):Graham 扫描法
2012-12-17 16:33 2201Graham扫描法 基本思想:通过设置一个关于候选点的 ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2173接上文:学习凸包(二) ... -
学习凸包(二):分治法求解
2012-12-16 14:32 3376接上文:学习凸包(一):暴力算法求解http://128kj. ... -
学习凸包(一):暴力算法求解
2012-12-15 17:06 2050凸包:令S是平面上的一个点集,封闭S中所有顶点的最小凸多边 ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1499关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1353接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1765关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1672关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1746关于树状数组,请参考:http://128kj.iteye.c ...
相关推荐
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
北大POJ1696-Space Ant 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1754177
NULL 博文链接:https://128kj.iteye.com/blog/1754170
NULL 博文链接:https://128kj.iteye.com/blog/1772172
NULL 博文链接:https://128kj.iteye.com/blog/1752661
北大POJ初级题-数据结构:解题报告+AC代码
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
NULL 博文链接:https://128kj.iteye.com/blog/1753387
NULL 博文链接:https://128kj.iteye.com/blog/1749213
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1759266
NULL 博文链接:https://128kj.iteye.com/blog/1757060
NULL 博文链接:https://128kj.iteye.com/blog/1744555
Printer Queue(打印队列)POJ3125 打印机顺序打印问题 这是一道ACM算法题,上面的两个是求打印时间,还有一种是求打印顺序 输入和输出: 输入 3 1 0 5 4 2 1 2 3 4 6 0 1 1 9 1 1 1 输出 1 2 5 问题解析 输入解析 第...
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
twilight-poj-solutionPOJ () solution by twilight想当年要找一题的分析, 解答实在太难了现在都是开源的时代了, 干脆把Archive放到GitHub上, 供后来人参考.POJ ID: 部分题解: 转载请注明出处~
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573