- 浏览: 601282 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
再次强调:
图的广度优先搜索,要遵守以下规则:
(0) 选取某一顶点作为开始搜索的起点(当前顶点),标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点,这个点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2,则搜索结束。
【题(poj 1101)】:给出一个地图,标有X的地方不能经过,给出一对坐标(2,3),(5,3),问这对坐标能否相连通(连连看),如果能则输出最少要经过的路段(路段是指一段直线,如果中途发生转折则就是两个路段);如果不能则输出impossible。
【注意】:
(1)本题的路可以在在给定的地图外走,如:W=5,H=4,则可选的路范围为0<=w<=W+1,0<=h<=H+1;
另外注意每一组测试数据在输出结果后要输出一行空行
(2)只有一个注意点该题搜的不是最短路径,而是最少拐弯次数(类似于连连看),再者要处理好地图与坐标的关系。
Sample Input
Sample Output
Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.
代码:
下载源码:
图的广度优先搜索,要遵守以下规则:
(0) 选取某一顶点作为开始搜索的起点(当前顶点),标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点,这个点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2,则搜索结束。
【题(poj 1101)】:给出一个地图,标有X的地方不能经过,给出一对坐标(2,3),(5,3),问这对坐标能否相连通(连连看),如果能则输出最少要经过的路段(路段是指一段直线,如果中途发生转折则就是两个路段);如果不能则输出impossible。
【注意】:
(1)本题的路可以在在给定的地图外走,如:W=5,H=4,则可选的路范围为0<=w<=W+1,0<=h<=H+1;
另外注意每一组测试数据在输出结果后要输出一行空行
(2)只有一个注意点该题搜的不是最短路径,而是最少拐弯次数(类似于连连看),再者要处理好地图与坐标的关系。
Sample Input
Sample Output
Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.
代码:
import java.util.*; class Piece{ //顶点类 int x, y; int step; //路段数 public Piece(){ this(0,0,0); } public Piece(int x,int y,int step){ this.x=x; this.y=y; this.step=step; } } public class Main{ private char g[][]; //地图 private int w, h; //地图的宽和高 private int dir[][] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; //四个方向,任意一点可能有四个邻接点(相通才是) private boolean visited[][]; private Piece start, goal; //起点和目标点 public Main(int w,int h, Piece start, Piece goal,char[][] g){ this.w=w; this.h=h; this.g=g; this.start=start; this.goal=goal; visited=new boolean[h+2][w+2]; } public Piece getGoal(){ return goal; } /* BFS访问与start最近的、相通(邻接)点并标记,路段数是1的是同一层,第一层完了再搜索第二层 路段数是2的是第二层,。。。(就一个四叉树而已)标记过的点不必再标记。*/ public void bfs(){ int i; Queue<Piece> que = new LinkedList<Piece>(); que.add(start); //起点入队 visited[start.x][start.y] = true; //标记为已访问 while(!que.isEmpty()) //队列非空 { Piece temp1 = que.poll(); //出队 if(temp1.x==goal.x && temp1.y==goal.y && goal.step>temp1.step) { goal.step = temp1.step; break;//如果搜索到了目标,程序退出。 } //访问temp1的四个邻接点,左、右、下、上 for(i=0; i<4; ++i) { Piece temp2=new Piece(); temp2.x = temp1.x + dir[i][0]; temp2.y = temp1.y + dir[i][1]; while(temp2.x>=0 && temp2.x<=h+1 && temp2.y>=0 && temp2.y<=w+1 && !visited[temp2.x][temp2.y] &&g[temp2.x][temp2.y]==' '){ //temp2与temp1相通 visited[temp2.x][temp2.y] = true; //标记为已访问 temp2.step = temp1.step+1; //同一方向上相通的点,路段数相同。 que.add(new Piece(temp2.x,temp2.y,temp2.step)); //入队 temp2.x += dir[i][0]; //在同一方向上继续走 temp2.y += dir[i][1]; } } } } public static void main(String args[]){ Scanner in=new Scanner(System.in); int nPacase=0; int nCase=0; Piece start=new Piece();//起点 Piece goal=new Piece();//目标点 while(true) { int w=in.nextInt(); int h=in.nextInt(); in.nextLine(); if(w==0&&h==0) break; char g[][]=new char[h+2][w+2]; for(int i=1; i<=h; ++i) { String line=in.nextLine(); for(int j=1; j<=w; j++) g[i][j]=line.charAt(j-1); //地图 } nPacase = 0; //外围加框 for(int i=0; i<=w+1; i++) { g[0][i] = ' '; g[h+1][i] = ' '; } for(int i=0; i<=h+1; ++i) { g[i][0] = ' '; g[i][w+1] = ' '; } //测试图的正确性 /* for(int i=0; i<=h+1; i++) { for(int j=0; j<=w+1; j++) System.out.print(g[i][j]); System.out.println(); } */ System.out.println("Board #"+(++nCase)+":"); while(1==1) { char[][] c=new char[h+2][w+2]; for(int i=0; i<=h+1; i++) { for(int j=0; j<=w+1; j++) c[i][j]=g[i][j]; //克隆数组 } start.y=in.nextInt(); start.x=in.nextInt(); goal.y=in.nextInt(); goal.x=in.nextInt(); start.step = 0; goal.step = Integer.MAX_VALUE; if(start.x==0 && start.y==0 && goal.x==0 && goal.y==0) //程序退出 break; if(c[goal.x][goal.y] == 'X') { c[goal.x][goal.y] = ' '; } Main m=new Main(w,h,start,goal,c); m.bfs(); if(m.getGoal().step == Integer.MAX_VALUE) System.out.println("Pair "+(++nPacase)+": impossible."); else System.out.println("Pair "+(++nPacase)+": "+m.getGoal().step+" segments."); } System.out.println(); } } }
下载源码:
发表评论
-
龙抬头
2014-11-10 15:06 621... -
求推箱子的最小步数(java)
2014-05-06 08:32 3746题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3054POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3314回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1836一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1923很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5927Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4045一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1242一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 2008先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2311一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2265继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4959深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1442如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之四
2012-10-16 15:26 1153例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1492广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之一
2012-10-13 15:27 1672有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2272凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1110最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ... -
动态规划算法学习十例之八
2012-10-05 15:14 1268矩阵链乘法最优结合问题 一、《问题的引出》 看下面一个 ...
相关推荐
【标题】:“广度优先搜索学习五例之四” 在计算机科学中,广度优先搜索(Breadth-First Search,简称BFS)是一种用于遍历或搜索树或图的算法。它按照从根节点开始,逐层进行探索的方式进行。在本案例中,我们可能...
**广度优先搜索(Breadth-First Search, BFS)**是一种在图或树中进行搜索的算法,常用于寻找最短路径或者遍历结构。它遵循“先探索节点的所有邻居,再探索邻居的邻居”的策略,从起点开始,逐层向外扩展。BFS的关键...
【标题】"广度优先搜索学习五例之三"涉及的是图论算法中的一个重要概念——广度优先搜索(Breadth-First Search, BFS)。在计算机科学中,BFS是一种用于遍历或搜索树或图的算法,尤其适用于查找最短路径问题。此标题...
在给定的"广度优先搜索学习五例之五"中,我们可能探讨的是一个具体的应用场景或者变体,但描述中并未提供详细信息。通常,BFS 的实现涉及以下几个关键元素: 1. **队列(Queue)**:BFS 使用队列作为主要的数据结构...
由于DFS具有深度优先的特点,它往往能在较深的分支找到解决方案,但可能会错过较浅的解,因此在某些情况下,如广度优先搜索(BFS)可能会是更好的选择。 总结来说,"深度优先搜索学习五例之四(JAVA)"的主题涵盖了...
在这个主题"深度优先搜索学习五例之一(JAVA)"中,我们可以期待看到至少五个不同的应用实例,这些实例将用Java语言实现,可能包括但不限于以下场景: 1. **图的遍历**:DFS可以用于遍历无向图或有向图,通过访问每...
例如,可能需要设计一个栈来实现后缀表达式的计算,或者利用队列进行广度优先搜索。通过实践,读者可以加深对数据结构的理解,提高代码的可读性和性能。 接着,算法是编程的灵魂。本书的编程题目中很可能包含排序...
2. **搜索算法**:如线性搜索、二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等,这些是解决查找问题的基础,对于理解数据结构至关重要。 3. **图论算法**:例如Dijkstra最短路径算法、Floyd-Warshall所有对...
- **广度优先搜索(BFS)**:使用队列数据结构,按照距离从起点到终点的顺序访问节点。 4. **动态规划(DP)**: - **斐波那契数列**:使用记忆化或自底向上的方法求解,避免重复计算。 - **背包问题**:如0-1背包...
2. **搜索算法**:二分查找、深度优先搜索、广度优先搜索等,探讨如何在数据结构中高效地查找目标元素。 3. **数据结构**:栈、队列、链表、树、图等,如何利用它们来实现各种算法。 4. **动态规划**:如斐波那契...
2. **搜索算法**:二分查找、线性查找、深度优先搜索(DFS)和广度优先搜索(BFS),这些算法在处理数据集合时非常实用。 3. **图论算法**:Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法,它们在网络...
在实现这个项目时,我们可能需要学习图算法,如深度优先搜索(DFS)或广度优先搜索(BFS),用于寻找从起点到终点的最短路径。数据结构如栈或队列会在这里发挥重要作用。同时,我们需要理解如何将迷宫表示为二维数组...
此外,文档中的其他实例可能包括搜索算法(如二分查找、广度优先搜索等)、图论算法(如Dijkstra最短路径、Floyd-Warshall算法等)以及动态规划、贪心算法等。学习这些算法不仅可以提升编程能力,还能培养解决问题的...
2. **搜索算法**:二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等,这些算法在处理数据查找和遍历树形结构时非常有效。 3. **图论算法**:最短路径问题(Dijkstra算法、Floyd算法),最小生成树(Prim算法...
这些代码可能包括简单的排序算法(冒泡、选择、插入、快速、归并等)、查找算法(顺序、二分、哈希等)、图算法(深度优先搜索、广度优先搜索、最小生成树、最短路径等)以及其他复杂的数据结构实现。 5. **学习...
这可能需要使用图遍历算法,如深度优先搜索(DFS)或广度优先搜索(BFS)。 3. **文件输入与输出**: - 输入通常包含每个建筑物的长、宽、高和位置信息,可能以CSV、JSON或其他格式存储。Java的`Scanner`类可用于...
2. **搜索算法**:如二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)。这些算法在处理大量数据时具有重要作用,如在树和图结构中寻找特定元素或路径。 3. **图论算法**:如Dijkstra最短路径算法、Floyd-...
3. **图论算法**:如深度优先搜索(DFS)和广度优先搜索(BFS),以及Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法等。 4. **动态规划**:解决许多复杂问题的有效方法,如背包问题、最长公共子序列、...
判断棋局胜负可能需要深度优先搜索(DFS)或广度优先搜索(BFS);而象棋的AI对战则可能涉及最小-最大搜索算法配合Alpha-Beta剪枝。 4. **状态管理**:棋盘上的每一步操作都会改变游戏的状态,这需要一个高效的数据...