- 浏览: 105870 次
- 性别:
- 来自: 广州
最新评论
-
xinhemei:
我试了试,发现gmail和163的不行。好像ajax请求失败了 ...
jQuery实现邮箱自动登录 -
酒鬼_yuan:
我正在找 谢谢了
关于yui的学习
问题重述:
背景
神话般的国际象棋玩家Somurolov先生,他声称,他可以把一个骑士从一个位置很快地移动到另一个位置,但其他人却不行。你能打败他吗?
存在的问题
你的任务是编写一个程序来计算的骑士达到从另一个位置所要移动的最少步数,这样你才有机会比Somurolov快。
也许人们不熟悉的国际象棋,骑士行动可能在如图1所示。
输入
首先在第一个行,输入n,表示有n种的情况。
接下来是n方案。每个方案包括三行。第一行指定一个棋盘边长L(4<=L<= 300)。整个棋盘的尺寸L *L.第二和第三行包含整数对(0,...,L - 1)*(0,...,L - 1)指定骑士开始和结束位置。整数对由一个空白分隔开。
输出
对于每个输入你要计算骑士的行动,有必要从起点移动到终点最少步数的情况。如果起点和终点都是平等的,距离是零。
2.解题过程:
分析过程:
当读懂了题意后,发现这可能是一道最短路径的应用,但当看到图算法的题目后,再仔细想下,这是一道广度优先遍历的应用,利用广搜去求最短路径比较简单。采用广度优先去搜索,一旦找到了就可以由搜索的深度去求出所需的最少步数。而广度优先的算法要用到队列,平时也做过练习,所以在算法上也就没有什么问题。而这道题的数据的输入问题,相对挺简单的。但存储就有点麻烦,因为棋盘的大小是从4*4到300*300,跨度比较大,如果只是定义最大的二维数组来存储,可能会浪费很多空间,此外,队列要存储的是一个棋盘的格子,所以要存至少两个数,为了方便,我直接使用两个整型的队列存储两个下标,感觉不难。
编程过程:
到了具体编程时,我才发现,如何由搜索的深度去求出所需的最少步数,这一步的实现挺麻烦的。我之前打算直接用以前写过的int型队列难以实现,除了要记录棋格的x,y坐标,还要记录棋格的步数。要不就只能重新定义一个新的结构体的队列,要不就得多个队列并行使用,但两者都挺麻烦的。所以我就想到如果我C++里有直接的队列可以使用,但我不会C++。最后发现poj上是可以提交java代码的,再想到下学期我得考sun的scjp认证,得复习下java。所以,最后打算用java来做。于是,我很快就用java把代码编出来了,自己测试也通过了,但提交时却说内存溢出。想了很久后,就大概猜到是什么原因,最初我是在得到size后就把整张棋盘都建了出来。这样就产生了很多的对象,自然多了许多没有用的对象霸占了许多内存。之后我就改为当需要时才去建棋格子的对象,果然少占了很多内存。但提交时,却发现运行错误,可是我自己测试却没问题,所以郁闷了很久。最后,发现有的地方会出现空指针异常,终于通过了。
3.做题收获:
通过这一道题,我找到了一个既可以练习java,又可以学到算法的途径,以后要多用java到poj上刷题才行。此外,我对java中的内存分配机制,有了更多的理解。题目虽然是通过了,但跟那些以前通过的人相比,我占用的内存还是太多了,这方面有待加强。用java做了题目后,我发现用C和java写代码,虽然用的算法是一样的,但对数据的输入与存储处理都有各自的优缺点。
程序源码
背景
神话般的国际象棋玩家Somurolov先生,他声称,他可以把一个骑士从一个位置很快地移动到另一个位置,但其他人却不行。你能打败他吗?
存在的问题
你的任务是编写一个程序来计算的骑士达到从另一个位置所要移动的最少步数,这样你才有机会比Somurolov快。
也许人们不熟悉的国际象棋,骑士行动可能在如图1所示。
输入
首先在第一个行,输入n,表示有n种的情况。
接下来是n方案。每个方案包括三行。第一行指定一个棋盘边长L(4<=L<= 300)。整个棋盘的尺寸L *L.第二和第三行包含整数对(0,...,L - 1)*(0,...,L - 1)指定骑士开始和结束位置。整数对由一个空白分隔开。
输出
对于每个输入你要计算骑士的行动,有必要从起点移动到终点最少步数的情况。如果起点和终点都是平等的,距离是零。
2.解题过程:
分析过程:
当读懂了题意后,发现这可能是一道最短路径的应用,但当看到图算法的题目后,再仔细想下,这是一道广度优先遍历的应用,利用广搜去求最短路径比较简单。采用广度优先去搜索,一旦找到了就可以由搜索的深度去求出所需的最少步数。而广度优先的算法要用到队列,平时也做过练习,所以在算法上也就没有什么问题。而这道题的数据的输入问题,相对挺简单的。但存储就有点麻烦,因为棋盘的大小是从4*4到300*300,跨度比较大,如果只是定义最大的二维数组来存储,可能会浪费很多空间,此外,队列要存储的是一个棋盘的格子,所以要存至少两个数,为了方便,我直接使用两个整型的队列存储两个下标,感觉不难。
编程过程:
到了具体编程时,我才发现,如何由搜索的深度去求出所需的最少步数,这一步的实现挺麻烦的。我之前打算直接用以前写过的int型队列难以实现,除了要记录棋格的x,y坐标,还要记录棋格的步数。要不就只能重新定义一个新的结构体的队列,要不就得多个队列并行使用,但两者都挺麻烦的。所以我就想到如果我C++里有直接的队列可以使用,但我不会C++。最后发现poj上是可以提交java代码的,再想到下学期我得考sun的scjp认证,得复习下java。所以,最后打算用java来做。于是,我很快就用java把代码编出来了,自己测试也通过了,但提交时却说内存溢出。想了很久后,就大概猜到是什么原因,最初我是在得到size后就把整张棋盘都建了出来。这样就产生了很多的对象,自然多了许多没有用的对象霸占了许多内存。之后我就改为当需要时才去建棋格子的对象,果然少占了很多内存。但提交时,却发现运行错误,可是我自己测试却没问题,所以郁闷了很久。最后,发现有的地方会出现空指针异常,终于通过了。
3.做题收获:
通过这一道题,我找到了一个既可以练习java,又可以学到算法的途径,以后要多用java到poj上刷题才行。此外,我对java中的内存分配机制,有了更多的理解。题目虽然是通过了,但跟那些以前通过的人相比,我占用的内存还是太多了,这方面有待加强。用java做了题目后,我发现用C和java写代码,虽然用的算法是一样的,但对数据的输入与存储处理都有各自的优缺点。
程序源码
package middle; import java.io.BufferedInputStream; import java.util.LinkedList; import java.util.Scanner; /* * To change this template, choose Tools | Templates * and open the template in the editor. */ /** * poj1915最初做这道题时,我是就c去做的,但到了具体编程时,我发现有些地方要用到 * 自定义类型的队列,自己去重写那些队列显行太麻烦了,本来C++就有现成的queue可以 * 用,但我没学过c++,所以就想到用java。代码也很快就写了出来,但提交时却说内存溢出 * 想了很久后,就大概猜到是什么原因,最初我是在得到size后就把整张棋盘都建了出来。 * 这样就产生了很多的对象,自然多了许多没有用的对象霸占了许多内存。之后我就改为 * 当需要时才去建棋格子的对象,果然少了很多内存。最后终于通过了。不过跟那些以前通过 * 的人相比,我占用的内存还是太多了。 * @author NC */ public class Poj1915 { private static int[][] directions = new int[][]{ {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}}; static void BreadthFirstSearch(int startX, int startY, chessNode[][] chessPanel, int size) { chessNode currentNode = null, nextNode = null; LinkedList<chessNode> queue = new LinkedList(); currentNode = chessPanel[startY][startY] = new chessNode(startX, startY, true, 0, false); queue.addLast(currentNode);//初始棋格入队 while (!queue.isEmpty()) { currentNode = queue.removeFirst();//出队 if (currentNode.isTarget()) {//如果走到了目的位置 break; } for (int i = 0; i < 8; i++) { //遍历八个方向 int x = currentNode.getX() + directions[i][0]; int y = currentNode.getY() + directions[i][1]; int step = currentNode.getStep(); if (x >= 0 && x < size && y >= 0 && y < size) { //如果棋格没有越界,并且没有访问过 if (chessPanel[x][y] == null) { chessPanel[x][y] = new chessNode(x, y, false, 0, false); } nextNode = chessPanel[x][y]; if (!nextNode.isVisited()) { nextNode.setVisited(true);//标记访问过 nextNode.setStep(step + 1);//记录步数 queue.addLast(nextNode);//入队 } } } } } public static void main(String[] args) { int n = 0; int size = 0; int startX = 0, startY = 0, endX = 0, endY = 0; Scanner scanner = new Scanner(new BufferedInputStream(System.in)); n = scanner.nextInt(); for (int i = 0; i < n; i++) { size = scanner.nextInt();//棋盘大小为size*size startX = scanner.nextInt();//初始位置x坐标 startY = scanner.nextInt();//初始位置y坐标 endX = scanner.nextInt();//目的位置x坐标 endY = scanner.nextInt();//目的位置y坐标 chessNode[][] chessPanel = new chessNode[size][size]; //设置目的位置true chessPanel[endX][endY] = new chessNode(endX, endY, false, 0, true); //广度优先遍历 BreadthFirstSearch(startX, startY, chessPanel, size); //输出最少步数 System.out.println(chessPanel[endX][endY].getStep()); } } } class chessNode { private int x; private int y; private boolean visited;//标记是否访问过 private int step;//记录从初始位置到当前棋格的最少步数 public int getX() { return x; } public chessNode(int x, int y, boolean visited, int step, boolean target) { this.x = x; this.y = y; this.visited = visited; this.step = step; this.target = target; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } private boolean target; public boolean isVisited() { return visited; } public void setVisited(boolean visited) { this.visited = visited; } public int getStep() { return step; } public void setStep(int step) { this.step = step; } public boolean isTarget() { return target; } public void setTarget(boolean target) { this.target = target; } }
发表评论
-
Poj3126
2010-05-29 22:07 1198import java.io.BufferedIn ... -
poj3125简单模拟
2010-05-25 11:44 917import java.io.BufferedInputS ... -
还是水
2010-05-24 12:53 729import java.io.BufferedInputS ... -
Poj3085再水一下
2010-05-24 12:28 820import java.io.BufferedInputS ... -
Poj3673超水题
2010-05-24 12:12 817package easy; import java. ... -
Poj3278 广度优先搜索
2010-05-22 23:24 1284import java.io.BufferedInputS ... -
合唱队形
2010-05-09 21:45 2101#include <stdio.h> #incl ... -
动态规划经典问题 石子合并
2010-05-09 21:45 6054我们学校的oj的 #include & ... -
poj3199 高精
2010-05-09 21:44 921import java.io.BufferedInputS ... -
poj1002 郁闷的电话号码
2010-05-08 23:48 1226import java.io.BufferedInputS ... -
poj1298 无语。。。
2010-04-24 23:24 973import java.io.BufferedInputStr ... -
poj1017 装箱问题 简单贪心
2010-04-18 16:56 2321import java.io.BufferedInpu ... -
poj1042 枚举+贪心算法
2010-04-18 00:45 1761import java.io.BufferedInputS ... -
zoj3197 Google Book 贪心算法
2010-04-15 23:54 1338#include <stdio.h> #defi ... -
Poj2453 an easy program
2010-04-09 00:19 830/* * To change this template, ... -
poj2299 递归与分治策略
2010-04-02 23:38 1396package hard; import java.io ... -
poj1723 数学问题
2010-04-02 15:31 989package middle; import jav ... -
Poj2524 并查集
2010-03-18 15:22 838package middle; import jav ... -
Poj1308 并查集
2010-03-18 15:21 1659package middle; import jav ... -
poj1405 高精
2010-02-28 11:09 1331import java.io.BufferedInputS ...
相关推荐
水题, 爆搜const int maxn = 105;
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
算法入门—广度优先搜索—raphealguo
(1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj...
Algorithm-Java Algorithms + Data ...图的深度优先遍历和广度优先遍历 最短路径(dijkstra,bellman-ford,floyd,heap+dijkstra)(,,poj1062,poj2253,poj1125,poj2240) 最小生成树(prim,kruskal)(p
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
模拟题 要注意时间的处理 使用优先队列处理请求的事件 进行适当的运算符重载,可以简化代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj2255代码8 4 给你前序遍历和中序遍历求后续遍历
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)