无标题文档

队列广度优先搜索

1.地图包围圈
 题目：
有一个长为m,宽为n的长方形地图，图上有一个不规则的小岛，小岛的海岸线被1标记出来了，也就是说小岛外面的0表示海水，小岛里面的0是陆地，请问小岛内被海岸线包围起来的0有多少个。已知m<100,n<100,且小岛外一定是海水包围着小岛的。 
 样例:
 输入:
23 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 1 1 1 0
0 0 0 1 0 1 0 0 0 1 1 0 0 1 0
0 0 1 0 0 1 1 0 1 0 0 0 1 0 0
0 0 1 0 0 0 1 0 1 1 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 1 1 0 0 0 0 0 0 0 1 1 0
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 1 1 1 0 0 1 0
0 1 0 0 0 0 0 0 1 0 1 0 0 1 0
0 0 1 1 0 0 1 0 1 0 1 0 1 1 0
0 0 0 0 1 1 1 0 1 0 1 0 1 0 0
0 0 0 0 1 0 0 1 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

输出:110
 
  
#include<iostream>
using namespace std;
int main(){
	int m,n,i,j,t,k,s=0,x,y;
	int a[100][100]={0},d[10000][2]={0};
	int p[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
	scanf("%d %d",&m,&n);
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j]==1)s++;
		}
	}
	k=0;x=0;y=0;
	d[0][0]=x;d[0][1]=y;
	a[x][y]=2;
    t=-1;
	while(t<=k){
		t++;
		for(i=0;i<4;i++){
			x=d[t][0]+p[i][0];
			y=d[t][1]+p[i][1];
			if(x>=0&&y>=0&&x<m&&y<n&&a[x][y]==0){
			   k++;
			   d[k][0]=x;d[k][1]=y;
			   a[x][y]=2;
			}
		}
		if(t==k)break;
	    
		
	}	
    printf("%d",m*n-s-k-1);
    return 0;
} 
 作业:
 1.细菌数
 在一个长方形的培养器上有一些水和细菌,现在0表示水,其他数字表示细菌的身体部分,如果一些非0数字上下左右相邻连成一体表示这是1个细菌,现在请统计有几个细菌. 
 输入规则:长m<100,宽n<100,第一行为长和宽,以下m行表示培养器上的水和细菌.
 输入:
 20 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 4 0 0 0 0 0 0 0 0
0 2 2 4 0 2 2 4 0 0 0 0 0 0 0
0 1 1 0 0 1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 0 6 0 0 0
0 0 0 0 0 0 2 1 0 0 4 5 3 0 0
0 0 0 0 0 0 0 0 0 0 0 2 2 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 2 2 2 2 0 0 0 0 0 0 0 0 0 0
0 2 2 2 2 0 0 0 0 0 0 0 0 1 0
0 0 1 2 2 0 0 0 0 0 0 0 0 2 3
0 0 2 2 0 0 0 0 0 0 0 0 0 0 3
0 0 2 0 0 0 0 0 1 2 5 0 0 0 0
0 0 0 0 0 0 0 0 0 1 5 2 0 0 0
0 0 0 0 5 2 2 0 2 1 1 1 0 0 0
0 0 0 0 4 2 2 0 2 0 1 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 输出:7

2.描述
这有一个迷宫，有0~8行和0~8列：

1,1,1,1,1,1,1,1,1
 1,0,0,1,0,0,1,0,1
 1,0,0,1,1,0,0,0,1
 1,0,1,0,1,1,0,1,1
 1,0,0,0,0,1,0,0,1
 1,1,0,1,0,1,0,0,1
 1,1,0,1,0,1,0,0,1
 1,1,0,1,0,0,0,0,1
 1,1,1,1,1,1,1,1,1

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入
第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。
输出
输出最少走几步。
样例输入
2
3 1  5 7
3 1  6 7
样例输出
12
11

解法一:深度优先搜索 ,时间长,效率差
// dfs深度优先搜索
#include <stdio.h>
int ans,sx,sy,ex,ey;
bool vis[9][9],map[9][9]={
 1,1,1,1,1,1,1,1,1,
 1,0,0,1,0,0,1,0,1,
 1,0,0,1,1,0,0,0,1,
 1,0,1,0,1,1,0,1,1,
 1,0,0,0,0,1,0,0,1,
 1,1,0,1,0,1,0,0,1,
 1,1,0,1,0,1,0,0,1,
 1,1,0,1,0,0,0,0,1,
 1,1,1,1,1,1,1,1,1
};

void dfs(int i,int j,int cnt)
{
    if(i<0||i>8||j<0||j>8||vis[i][j]||map[i][j]||cnt>=ans)return;
    if(i==ex&&j==ey)
    {
        ans=cnt;
        return;
    }

vis[i][j]=1;       // 这个已经遍历了x`

dfs(i,j-1,cnt+1);
    dfs(i-1,j,cnt+1);
    dfs(i,j+1,cnt+1);
    dfs(i+1,j,cnt+1);

vis[i][j]=0;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
        ans=100;
        dfs(sx,sy,0);
        printf("%d\n",ans);
    }
    return 0;
}
解法2:效率高,时间短
/*BFS广度优先搜索 */
#include<cstdio>
#include<cstring>
using namespace std;

#define N 9

typedef struct
{
   // int x,y,cnt;
}Node;

int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int sx,sy,ex,ey;
int mp[N][N] =
{
    {1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,1,0,1},
    {1,0,0,1,1,0,0,0,1},
    {1,0,1,0,1,1,0,1,1},
    {1,0,0,0,0,1,0,0,1},
    {1,1,0,1,0,1,0,0,1},
    {1,1,0,1,0,1,0,0,1},
    {1,1,0,1,0,0,0,0,1},
    {1,1,1,1,1,1,1,1,1}
};
int vis[N][N];
int bfs()
{
   int Qx[10000]={0},Qy[10000]={0},Qcnt[10000]={0};
   
    int k=0,px,py,pcnt,tmpx,tmpy,tmpcnt;
    Qx[0]=sx;Qy[0]=sy;Qcnt[0]=0;
   
    memset(vis,0,sizeof(vis));
    vis[sx][sy] = 1;
    
    while(k>=0)
    {
    	px= Qx[k];
    	py=Qy[k];
    	pcnt=Qcnt[k];
        k--;
        if (px == ex && py == ey)
            return pcnt;

for(int di=0;di<4;di++)
        {
            tmpx = px + dir[di][0];    tmpy = py + dir[di][1];
            tmpcnt = pcnt + 1;
            if(tmpx>=0 && tmpx<=8 && tmpy>=0 && tmpy<=8 &&!vis[tmpx][tmpy] && !mp[tmpx][tmpy] )
            {
               k++;
               Qx[k]=tmpx;
               Qy[k]=tmpy;
               Qcnt[k]=tmpcnt;
                vis[tmpx][tmpy] = 1;
            }
        }
    }
    return -1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
        printf("%d\n",bfs());
    }
    return 0;
}

解法3:
/*同样BFS广度优先搜索 只是用 队列数组Queue的入队和出队的封装函数,定义结点类型,从而减少编写代码量,更简洁  */
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

#define N 9

typedef struct
{
    int x,y,cnt;
}Node;

int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int sx,sy,ex,ey;
int mp[N][N] =
{
    {1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,1,0,1},
    {1,0,0,1,1,0,0,0,1},
    {1,0,1,0,1,1,0,1,1},
    {1,0,0,0,0,1,0,0,1},
    {1,1,0,1,0,1,0,0,1},
    {1,1,0,1,0,1,0,0,1},
    {1,1,0,1,0,0,0,0,1},
    {1,1,1,1,1,1,1,1,1}
};
int vis[N][N];
int bfs()
{
    queue<Node> Q;
    Node tmp,p;
    p.x = sx;    p.y = sy;
    p.cnt = 0;
    memset(vis,0,sizeof(vis));
    vis[sx][sy] = 1;
    Q.push(p);
    while(!Q.empty())
    {
        p = Q.front();
        Q.pop();
        if (p.x == ex && p.y == ey)
            return p.cnt;

for(int di=0;di<4;di++)
        {
            tmp.x = p.x + dir[di][0];    tmp.y = p.y + dir[di][1];
            tmp.cnt = p.cnt + 1;
            if(tmp.x>=0 && tmp.x<=8 && tmp.y>=0 && tmp.y<=8 &&!vis[tmp.x][tmp.y] && !mp[tmp.x][tmp.y] )
            {
                Q.push(tmp);
                vis[tmp.x][tmp.y] = 1;
            }
        }
    }
    return -1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
        printf("%d\n",bfs());
    }
    return 0;
}

3. 广度优先走迷宫找最短路径
#include<iostream> 
using namespace std;

void EnQueue(int i,int j,int k); //入队一个节点 
void DeQueue(int *i,int *j,int *k); //获取当前节点的序号和对应的迷宫坐标，然后出列 
bool GetNextPos(int *i ,int *j,int count); //得到下一个邻接点的位置 
void ShortestPath_BFS(int i,int j); //广度优先遍历寻找最短路径 
void ShortestPath(); //输出最短路径 
void Print(); //输出迷宫形状

int Map[10][10] = {{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,0},{1,1,1,1,1,1,1,1,1,1}};

struct Node 
{ 
int parent_id; //保存父节点的位置 
int node_id; //当前节点的序号，以便传递给孩子节点 
int x,y; //当前结点对应的坐标 
}Q[10*10]; //每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列

int front = 0,rear = 0; //队列头指针和尾指针

int main() 
{ 
cout<<"程序说明："<<'\n'<<"1.输出路径为最短路径；"<<'\n'<<"2.默认的出口在最右下角，如有需要可以调整。"<<'\n'<<'\n'; 
cout<<"初始地图如下："<<endl; 
Print(); 
int i,j;

reinput: cout<<"请输入起点坐标（x,y）： "<<endl; cin>>i>>j;

if(Map[i][j]) 
{
cout<<"不能从该处出发，请重新输入！"<<endl;goto reinput;
} 
ShortestPath_BFS(i,j); cout<<"最短路径之一如下："<<endl;
ShortestPath(); 
}

void EnQueue(int i,int j,int k) //入队一个节点
{ 
Q[rear].x = i; 
Q[rear].y = j; //保存当前节点对应的坐标位置
Q[rear].parent_id = k; //保存父节点的序号 ************-1
Q[rear].node_id = rear; //保存当前节点序号 
rear++;
}

void DeQueue(int *i,int *j,int *k) //获取当前节点的序号和对应的迷宫坐标，然后出列
{
*i = Q[front].x; 
*j = Q[front].y; 
*k = Q[front].node_id; 
front++; //出列一个节点
}

bool GetNextPos(int *i ,int *j,int count) //得到下一个邻接点的位置 
{
switch(count) 
{
case 1:(*j)++; return 1; //右
case 2:(*i)++; return 1; //下
case 3:(*j)--; return 1; //左
case 4:(*i)--; return 1; //上
default: 
return 0; 
} 
}

void ShortestPath_BFS(int i ,int j) //广度优先遍历寻找最短路径 
{
int count,m,n,k; 
EnQueue(i,j,-1); 
Map[i][j] = 1; //起点入队，标记起点已走过
while(true)
{
count = 1; 
DeQueue(&i,&j,&k); 
n = i,m = j; 
//保存当前位置
while(GetNextPos(&i,&j,count)) 
{
count++; 
if(!Map[i][j]) 
{ 
EnQueue(i,j,k); 
Map[i][j] = 1; 
if(i == 8 && j == 9) 
return; //到达终点（8,9）是默认终点，可以任意修改
}

i = n; j = m; //保证遍历当前坐标的所有相邻位置
}
}

}

void ShortestPath() 
{
int i,j,k,sum=0;
k = rear-1; 
while(k != -1) 
{
i = Q[k].x; 
j = Q[k].y;
Map[i][j] = 2; 
k = Q[k].parent_id; 
}
cout<<" 0 1 2 3 4 5 6 7 8 9"<<endl;

for(i = 0;i < 10;i++) 
{
cout<<i; 
for(j = 0;j < 10;j++)
{
if(Map[i][j]==2) 
{sum++; cout<<"□";} 
else 
cout<<"■"; 
}
cout<<endl; 
}

cout<<"最短路径长度："<<sum<<endl; 
}

void Print() 
{
cout<<" 0 1 2 3 4 5 6 7 8 9"<<endl; 
for(int i = 0;i < 10;i++) 
{
cout<<i; 
for(int j = 0;j < 10;j++) 
{
if(Map[i][j]) 
cout<<"■"; 
else 
cout<<"□"; 
}
cout<<endl; 
} 
}

程序说明：
1.输出路径为最短路径；
2.默认的出口在最右下角，如有需要可以调整。

初始地图如下：
 0 1 2 3 4 5 6 7 8 9
0■■■■■■■■■■
1■□□■□□□■□■
2■□□■□□□■□■
3■□□□□■■□□■
4■□■■■□□□□■
5■□□□■□□□□■
6■□■□□□■□□■
7■□■■■□■■□■
8■■□□□□□□□□
9■■■■■■■■■■
请输入起点坐标（x,y）：
1 1
最短路径之一如下：
 0 1 2 3 4 5 6 7 8 9
0■■■■■■■■■■
1■□■■■■■■■■
2■□■■■■■■■■
3■□■■■■■■■■
4■□■■■■■■■■
5■□□□■■■■■■
6■■■□□□■■■■
7■■■■■□■■■■
8■■■■■□□□□□
9■■■■■■■■■■
最短路径长度：16