时间:2008-06-02 21:05:08   来源:论坛整理  作者:  编辑:chinaitzhe

初学算法，谁帮忙讲讲BFS 和 DFS并解一下下面这题
万分感谢

zoj
One morning, you wake up and think: ``I am such a good programmer. Why not make some money?'' So you decide to write a computer game.

The game takes place on a rectangular board consisting of w * h squares. Each square might or might not contain a game piece, as shown in the picture.

One important aspect of the game is whether two game pieces can be connected by a path which satisfies the two following properties:

It consists of straight segments, each one being either horizontal or vertical.

It does not cross any other game pieces.

(It is allowed that the path leaves the board temporarily.)

Here is an example:

The game pieces at (1,3) and at (4, 4) can be connected. The game pieces at (2, 3) and (3, 4) cannot be connected; each path would cross at least one other game piece.

The part of the game you have to write now is the one testing whether two game pieces can be connected according to the rules above.


Input

The input contains descriptions of several different game situations. The first line of each description contains two integers w and h (1 <= w,h <= 75), the width and the height of the board. The next h lines describe the contents of the board; each of these lines contains exactly w characters: a ``X'' if there is a game piece at this location, and a space if there is no game piece.

Each description is followed by several lines containing four integers x1, y1, x2, y2 each satisfying 1 <= x1,x2 <= w, 1 <= y1,y2 <= h. These are the coordinates of two game pieces. (The upper left corner has the coordinates (1, 1).) These two game pieces will always be different. The list of pairs of game pieces for a board will be terminated by a line containing ``0 0 0 0".

The entire input is terminated by a test case starting with w=h=0. This test case should not be procesed.


Output

For each board, output the line ``Board #n:'', where n is the number of the board. Then, output one line for each pair of game pieces associated with the board description. Each of these lines has to start with ``Pair m: '', where m is the number of the pair (starting the count with 1 for each board). Follow this by ``ksegments.'', where k is the minimum number of segments for a path connecting the two game pieces, or ``impossible.'', if it is not possible to connect the two game pieces as described above.

Output a blank line after each board.


Sample Input

5 4
XXXXX
X X
XXX X
XXX
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
0 0


Sample Output

Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.
网友回复:zoj 1148

网友回复:广度优先搜索(Breadth-First-Search)和深度优先搜索(Deep－First－Search)是搜索策略中最经常用到的两种方法,非凡常用于图的搜索.其中有很多的算法都用到了这两种思想,比如:Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

BFS的思想：
从一个图的某一个顶点V0出发，首先访问和V0相邻的且未被访问过的顶点V1、V2、……Vn，然后依次访问与V1、V2……Vn相邻且未被访问的顶点。如此继续，找到所要找的顶点或者遍历完整个图。
由此可以看出，用BFS进行搜索所搜索的顶点都是按深度进行扩展的，先找到到V0距离为1的所有顶点，然后找到距离V0为2的顶点……所以BFS所搜索到的都是最短的路径。
由于要将距离V0为d(d>0)的且未被方位的点都记录起来，我们采用队列这种数据结构。队列的特点是先进先出(FIFO)，从某个顶点出发，记此顶点已访问标记，然后依次搜索和此顶点相邻的且未被访问的顶点，将其加入队列，并置已访问标记，重复此步骤，直到找到需要搜索的顶点或者所有的顶点都被访问为止。
算法的基本流程如下：
procedure BFS(i);
begin
write(i);
visited[i]:=true;
insert(q,i);{q是队列，i进队}
repeat
k:=delete(q)；{出队}
for j:=1 to n do
if (a[k,j]=1) and (not visited[j]) then
begin
write(j);
visited[j]:=true;
insert(q,j);
end;
until 队列q为空;
end.

DFS的思想：
顾名思义，深度优先搜索所遵循的策略就是尽可能“深”的在图中进行搜索，对于图中某一个顶点V，假如它还有相邻的顶点（在有向图中就是还有以V为起点的边）且未被访问，则访问此顶点。假如找不到，则返回到上一个顶点。这一过程一直进行直到所有的顶点都被访问为止。 DFS可以搜索出从某一个顶点到另外的一个顶点的所有路径。 由于要进行返回的操作，我们采用的是递归的方法。
其基本算法流程如下：
procedure DFS(V0)
begin
visite(V0);
visited[V0]=true;
for j:=1 to n do
if (a[V0,j]=1) and (not visited[j]) then
DFS(j);
end;

//采用邻接表为存储结构
void dfs(algraph *g,int v)
{
arcnode *p;
visited[v]=1; //置已访问标记
cout < <v; //访问节点
p=g->adjlist[v].firstarc; //p指向顶点v的第一条弧的节点
while(p!=NULL){
if(visited[p->adjvex]==0)//若p->adjvex顶点没有访问，递归进行访问
dfs(g,p->adjvex);
p=p->nextarc; //p指向顶点v的下一条弧的弧头节点
}
}

下面举一个具体的例子来说明一下BFS和DFS的应用。

题目描述：给一个M×N的迷宫，里面有宝藏（'o'表示,此位置可走）、墙（'#'表示,是不能走的位置)和空位 置 ('.'表示,可走),现在要求从迷宫的左上角出发，在最短的步数里面找到K个宝藏(K给定),每一步可以走当前位置的上下左右四个相邻的位置.

现给定迷宫和K(K <=迷宫中o点的数目),返回最小的步数,不能满足要求则返回-1.

Example:
1)
.....
o....
o....
o....
...o.
3
Returns: 3 (从左上角直接往下走三步即可)

2)
.#...
#....
...oo
...oo
...oo
1
Returns: -1
because can't move from the starting location.


3)
...o.
o..o.
.....
..oo.
.....
4
Returns: 7

4)
....#
.##o#
.##oo
o##.#
....#
4
Returns: 12



解答:
此题是topcoder的一道题目。 第一印象就是感觉有点像一个图的问题，感觉可以用图论的方法来解决。不过我觉得此题似乎有更简单的方法，如用动态规划(DP)，可是想不出来，哪位有想法，麻烦告诉一声，呵呵。
现在我们用BFS和DFS来解决这个问题：先用BFS求出每两个o点的最短距离，然后用DFS对所有o点进行搜索，找出经过K个o点的最小步数。

//001-100 01-10 10 in java language
import java.util.LinkedList;

class Point
{
public int x;
public int y;
public Point(int x,int y)
{
this.x=x;
this.y=y;
}
}
public class Doorknobs
{
public static int[][] move={{1,0},{-1,0},{0,1},{0,-1}};//在迷宫中可走的四个方向
public Point[] point; //记录迷宫中的o点
public int[][] dist; //记录任意两个o点的距离
public boolean[] used; //用于DFS时作已访问标记
public int count; //记录o点的个数
public char[][] ch; //迷宫的描述

public Doorknobs() //初始化
{
point=new Point[10];
dist=new int[10][10];
used=new boolean[10];
ch=new char[51][51];
count=0;
}

//BFS求Point(x1,y1)和Point(x2,y2)的最短距离
public int distance(String[] house,int x1,int y1,int x2,int y2)
{
int row=house.length;
int col=house[0].length();
int deep=0; //记录最短距离

for(int i=0;i <row;i ) //将String[]转化为char的二维数组
{
ch[i]=house[i].toCharArray();
}

LinkedList queue=new LinkedList(); //用LinkedList实现队列
ch[x1][y1]='#'; //置访问标志
queue.add(new Point(x1,y1));
queue.add(null); //null为BFS搜索一层的标志
while(!queue.isEmpty())
{
Point p;
while((p=(Point)queue.poll())!=null)
{
int x=p.x;
int y=p.y;
if(x==x2 && y==y2) //找到
{
return deep;
}
for(int i=0;i <4;i )
{
int nx=x move[i][0];
int ny=y move[i][1];
if(nx <0 ¦ ¦ nx>=row ¦ ¦ ny <0 ¦ ¦ ny>=col ¦ ¦ ch[nx][ny]=='#')
{
continue;
}
ch[nx][ny]='#'; //置访问标志
queue.add(new Point(nx,ny)); //加入队列
}
}
deep ;
queue.add(null);

}
return Integer.MAX_VALUE;
}

//从第start个点开始找left个点的最短距离
public int dfs(int start,int left)
{
int ret=Integer.MAX_VALUE;
for(int i=0;i <count;i )
{
if(!used[i])
{
int temp=dist[start][i];
if(left!=1)
{
used[i]=true;
temp =dfs(i,left-1);
used[i]=false;
}
if(temp <ret)
{
ret=temp;
}
}
}
return ret;
}
public int shortest(String[] house, int doorknobs)
{
int row=house.length;
int col=house[0].length();
int i=0,j=0;
for(i=0;i <row;i )
{
for(j=0;j <col;j )
{
if(house[i].charAt(j)=='o')
{
point[count]=new Point(i,j);
count ;
}
}
}
point[count]=new Point(0,0);//初始点
count ;

//dist[i][j]==dist[j][i],可以进行优化一下
for(i=0;i <count;i )
{
for(j=0;j <count;j )
{
dist[i][j]=distance(house,point[i].x,point[i].y,point[j].x,point[j].y);
//System.out.println (i " " j " " dist[i][j]);
}
}

used[count-1]=true;
int ret=dfs(count-1,doorknobs);
return (ret==Integer.MAX_VALUE)? -1 : ret;
}

public static void main(String args[])
{
Doorknobs d=new Doorknobs();
String house[]={".....","o....","o....","o....","...o."};
System.out.println (d.shortest(house,4));
}
}



再补上一个C 语言版本的：

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <ctime>
using namespace std;
#define MAX 51

char house[MAX][MAX];
int m,n,k,totalKey,best;
int dis[MAX][MAX];
int x[51],y[51];
bool used[51];
struct Point
{
int x;
int y;
int len;
};

void readData(int m,int n)
{
int i,j;
x[0]=0;
y[0]=0;
totalKey ;
for(i=0; i <m; i )
{
scanf("%s",house[i]);
for(j=0; j <n; j )
{
if(house[i][j]=='o')
{
x[totalKey]=i;
y[totalKey]=j;
totalKey ;
}
}
}
}


int compute(int xa, int ya, int xb, int yb)
{
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
bool visited[MAX][MAX] = {false};
queue <Point> q;
Point p;
p.x = xa;
p.y = ya;
p.len = 0;
q.push(p);
visited[xa][ya] = true;

while(!q.empty())
{
Point top = q.front();
q.pop();

if(top.x == xb && top.y == yb)
{
return top.len;
}
for(int i=0; i <4; i )
{
int xx = top.x dx[i];
int yy = top.y dy[i];
if(xx >= 0 && xx < m && yy >=0 && yy <n && !visited[xx][yy] && house[xx][yy]!='#')
{
Point tmp;
tmp.x = xx;
tmp.y = yy;
tmp.len = top.len 1;
q.push(tmp);
visited[xx][yy] = true;
}
}
}
return -1;
}

void computedis()
{
int i,j;
for(i=0;i <totalKey;i )
{
dis[i][i]=0;
for(j=i 1;j <totalKey;j )
{
int d = compute(x[i],y[i],x[j],y[j]);
dis[i][j]=dis[j][i]=d;
//cout < <"dixtance " < <i < <" " < <j < <" :" < <d < <endl;
}
}
}

//从第currentKey个开始，还需找left个，找到的长度(步数)为len
void find(int currentKey, int left, int len)
{
if(len>=best) return; //剪枝
if(left == 0)
{
if(len < best ¦ ¦ best == -1)
{
best = len;
//cout < <len < <endl;
}
return;
}
for(int i=1; i < totalKey; i )
{
if(i != currentKey && !used[i] && dis[currentKey][i] != -1)
{
used[i] = true;
find(i,left-1,len dis[currentKey][i]);
used[i] = false;
}
}
}

int main()
{
int i;
//double t = clock();
while(scanf("%d%d%d",&m,&n,&k)!=EOF)
{
totalKey = 0;
readData(m,n);
computedis();
best = 100000;
for(i=0; i <totalKey; i )
{
used[i] = false;
}
used[0]=true;
find(0,k,0);
if(best == 100000) best = -1;
cout < <best < <endl;
}
//cout < <(clock()-t)/CLK_TCK < <endl;
}


网友回复:Ⅰ 深度优先搜索(depth first search)的简称

深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.

深度优先搜索
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。优点是能遍历一个Web 站点或深层嵌套的文档集合；缺点是因为Web结构相当深,，有可能造成一旦进去，再也出不来的情况发生。

(进化论密码按:由于以上一段描述本人不能看懂,所以暂时保留之.)

事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.

举例说明之:下图是一个无向图,假如我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到 A,A也没有未访问的相邻节点,本次搜索结束).

B--E
/
A-C--F
\ >H
D--G

简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.假如将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的"拓扑排序",即topological sort.

当然,当人们刚刚把握深度优先搜索的时候经常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索 (BFS).状态（state):状态是制问题求解过程中每一步的状况。
算符（operater）算符是把问题从一种状态变换到另一种状态的方法代号。算符的屈指范围就是搜索的范围。（一般设为局部变量)。
节点（node）:用来表明状态特征及相关信息。

Ⅱ Distributed File System (DFS)
是关于MICROSOFT WORD 的某帮助治理文档，文件夹的软件。
原文解释：
Distributed file system (Dfs) is a service that allows system administrators
to organize distributed network shares into a logical namespace, enabling users to access
files without specifying their physical location and providing load sharing across network
shares. You can use Distributed File System (DFS) to build an easily browsed structure
for all the shared folders on your network. After users connect to the root DFS share, they
can browse shared resources regardless of the server that hosts the share.

Ⅲ DUTY FREE SHOPPING。
免税消费。

DFS（分布式文件系统）

在大多数环境中，共享资源驻留在多台服务器上的各个共享文件夹中。要访问资源，用户或程序必须将驱动器映射到共享资源的服务器，或指定共享资源的通用命名约定 (UNC) 路径。例如：
\\服务器名\共享名
或
\\服务器名\共享名\路径\文件名
通过 DFS（分布式文件系统），一台服务器上的某个共享点能够作为驻留在其他服务器上的共享资源的宿主。DFS 以透明方式链接文件服务器和共享文件夹，然后将其映射到单个层次结构，以便可以从一个位置对其进行访问，而实际上数据却分布在不同的位置。用户不必再转至网络上的多个位置以查找所需的信息，而只需连接到：\\DfsServer\Dfsroot
用户在访问此共享中的文件夹时将被重定向到包含共享资源的网络位置。这样，用户只需知道 DFS 根目录共享即可访问整个企业的共享资源。
DFS 拓扑从 DFS 树的根目录开始。位于逻辑层次结构顶部的 DFS 根目录映射到一个物理共享。DFS 链接将域名系统 (DNS) 名称映射到目标共享文件夹或目标 DFS 根目录的 UNC 名称。当 DFS 客户端访问 DFS 共享文件夹时，DFS 服务器将 DNS 名称映射到 UNC 名称并将引用返回给该客户端，以使它能够找到共享文件夹。将 DNS 名称映射到 UNC 名称使数据的物理位置对用户是透明的，这样用户便无须记住存储文件夹的服务器。当 DFS 客户端请求 DFS 共享的引用时，DFS 服务器将使用分区情况表 (PKT) 将 DFS 客户端定向到物理共享。对于基于域的 DFS，PKT 存储在 Active Directory 中；对于独立的 DFS，PKT 存储在注册表中。在网络环境中，PKT 维护有关 DFS 拓扑的所有信息，包括其到基础物理共享的映射。DFS 服务器将 DFS 客户端定向到与请求的 DFS 链接相对应的副本共享列表后，DFS 客户端使用 Active Directory 站点拓扑连接到同一站点中的一个副本，假如该站点中没有提供副本，则连接到该站点以外的一个副本。
网友回复:广度优先搜索

每次将集合中的元素经过一些改动，分层生成当前状态的子状态（通常还删除父情况），添加到集合（队列）中，以实现遍历或搜索等目的的算法。

Pseudocode (用队列)
1 procedure(state)
2 for each possible next state from this one
3 enqueue next state
4 search()
5 enqueue initial state
6 while not empty(queue)
7 state->get state from queue
8 process(state)

基本思想

（1）建立一个空的状态队列SS；
（2）建立一个空的状态库SB；
（3）把初始状态S（0）存入队列SS中；
（4）若队列状态是目标状态，则搜索成功，算法运行中止。如该状态的形式为S（path)，则解就是（path);
（5）若某种搜索极限已经达到（如空间用完等），则搜索失败，算法运行结束，没有解；
（6）按某种原则取一个可以应用于SS第一个状态S(path)并产生合适的新状态的规则Rn，产生新状态T(path,n),并将其置于SS的最后，转（4）。若扩展失败，即没有新状态产生，则将SS中第一个状态从SS中除去，送入SB中，执行下步；
（7）若SS成为空队列，则搜索失败，算法运行结束，没有解。否则转（5）。
网友回复:东西是好，但还需琢磨琢磨。有谁能结合我说的那题讲解一下吗？
网友回复:

这个题目，用深度和用广度都可以解。
相对而言，用广度更加合适。
楼主是想要代码吗？ 恩。。。 也不难，等我先去吃饭。

网友回复:谢谢啊。麻烦给代码弄点注释......
网友回复:我有代码~，假如需要，请找我！
网友回复:假如能和我讲讲思路就行了。。。不行的话再看代码吧
网友回复:那我还是讲思路好了

比如，如图

XXXXX
X X
XXX X
XXX

2 3 5 3

从出发点（2，3）开始，将它四周可以走的地方标上步数
第一步：
XXXXX
X1 X
XXX X
XXX
第二步
XXXXX
X12 X
XXX X
XXX
第三步
XXXXX
X123X
XXX X
XXX
第四步
XXXXX
X123X
XXX4X
XXX



网友回复:这样做不是要遍历所有可能吗。只不过你的图刚好有点非凡而已
网友回复:这个图帮我标记一下
：
XXXX
X X
XX X
X

从(1,2)到(4,4)
网友回复:XXXX
X X
XX X
X
网友回复:晕绑定
网友回复:图写错了.
XXXX
X X
XX X
X
网友回复:XXXX
X X
XX X
X

从(1,2)到(4,4)

首先从(1,2) 出发， 将其四周的4个方向的空格标为1
XXXX
X1 X
XX X
X
接着将1四周的空格标为2
XXXX
X12X
XX X
X
再将2四周的空格标为3
XXXX
X12X
XX3X
X
再将3四周的空格标为4
XXXX
X12X
XX3X
4X
到第5步的时候，终点已经在4的四周了