宽度优先搜索.ppt

宽度优先搜索
走迷宫(Maze)
【问题描述】
已知一N×N的迷宫,允许往上、下、左、右四个方向行走,现请你找出一条从左上角到右下角的最短路径。
【输入数据】
输入数据有若干行,第一行有一个自然数N(N≤20),表示迷宫的大小,其后有N行数据,每行有N个0或1(数字之间没有空格,0表示可以通过,1表示不能通过),用以描述迷宫地图。入口在左上角(1,1)处,出口在右下角(N,N)处。所有迷宫保证存在从入口到出口的可行路径。
【输出数据】
输出数据仅一行,为从入口到出口的路径(有多条路径时输出任意一条即可请严格按照下上左右)。路径格式参见样例。
【样例输入】
4
0001
0100
0010
0110
【样例输出】(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)
#include<iostream>
using namespace std;
const int dx[5]={0,1,-1,0,0};
const int dy[5]={0,0,0,1,-1};
int a[20],b[20];int c[20][20];
int n;
int main()
{
string s;
int i,j;
cin>>n;
for (i=1;i<=n;++i)
{
cin>>s;
for (j=0;j<();++j)
if (s[j]=='0') c[i][j+1]=0;
else c[i][j+1]=1;
}
dfs(1,1,1);
}
void print(int dep)
{
int i;
for (i=1;i<dep;i++)
cout<<"("<<a[i]<<","<<b[i]<<")->";
cout<<"("<<a[i]<<","<<b[i]<<")"<<endl;
}
void dfs(int dep,int x,int y)
{ int i,tx,ty;
a[dep]=x;
b[dep]=y;
c[x][y]=1;
if(x==n&&y==n) print(dep);
else for (i=1;i<=4;i++)
{
tx=x+dx[i];
ty=y+dy[i];
if (tx>0&&tx<=n&&ty>0&&ty<=n&&c[tx][ty]==0)
dfs(dep+1,tx,ty);
}

}
算法1:dfs
从左上角开始,找到下一个能走的路c[i][j]=0,然后dfs(i,j),(接着穷举i,j)下一个点继续dfs,直到找到出口位置。
算法2:bfs(宽度优先搜索)_利用队列实现
入队
出队
A1 A2 A3 A4 A5 A6
A1
A7
队列的概念
队列和栈一样,也是一种特殊的线性表;
队列是一种运算受到限制的线性表,插入操作限定在表的一端进行,称为“入队”,删除操作则限定在表的另一端进行,称为“出队”;
插入一端称为队尾(rear),删除一端称为队头(front)。
队头
队尾
队列的概念
队列的特点:先进队列的元素先出队列;
队列常说成先进先出线性表(FIFO,First In First Out);
类似于生活中排队购票:先来先买,后来后买。
队列的存储结构
在计算机中实现(存储)队列的最简单方法是用一维数组;
若每个节点需要存储的不只一个数据,则可以把每个数组元素的基类型设置为记录;或者定义成多个一维数组,再或者定义成一个几行n列的二维数组;
为了标识队头和队尾,还要设置两个下标(指针)变量front和rear,分别指向队列的头和尾。
周末舞会
假设在周末舞会上,男士们和女士们进入舞厅时,各自排成一队。跳舞开始时,依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同,则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序,模拟上述舞伴配对问题。
输入:
3个整数m,n,k,分别表示男士人数、女士人数、几轮舞曲。
输出:
各轮舞曲的配对方案。