BFS广度优先搜索

DFS深度优先搜索参见 DFS

代码分析

常用代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;  //pair<int,int> 是将两个int类型的数合为一个，本质上是结构体
queue<PII> q; //创建一个队列，名为q，类型是pair<int,int>（上方定义为PII）
PII temppair; //创建临时pair以储存从队列弹出的数据
int Map[N][N]; //创建地图，注意不要写map
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1}; 
int len; // *有时候会用到，比如长草那道题，需要用来判断这次扩张是否结束。
/*
dx和dy数组是把Map地图区域划分成如下的两个轴：
—————————————————> y
|
|
|
↓
x
将二维数组arr[n][m]看成n*m的，一个单位为1的网格
左上角是(0,0)，往下走是(1,0)，往右走是(0,1)
dx[0]=1,dy[0]=0 表示向下，其余同理
*/
bool pd(int x,int y)
{
    if(//通常最基本的条件是不能越界)
        return false;
    if(//也可能判断取到的地方有没有去过)
        return false;
    return true;
}
void bfs()
{
    while(!q.empty)  
    {
        temppair = q.front(); //取队列第一个值
        q.pop(); //并把它删除
        for(int i=0;i<4;i++)
        {
            int nowx=temppair.first+dx[i];  //从这个节点开始向上下左右取数
            int nowy=temppair.second+dy[i];
        	if(pd(nowx,nowy)) //判断那个位置能不能满足要求
            {
                //满足要求后..
            }
            
        }
    }
}

int main()
{
	// 函数主体，包括读入数据，创建地图等...
    int x1,y1; //假定这里读入一个初始坐标
    q.push({x1,y1}); //把它压入队列
    bfs();
    // 输出...
    return 0;
}

例题分析

求细胞数量

题干

题目描述

一矩形阵列由数字 0 到 9 组成，数字 1 到 9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

输入格式

第一行两个整数代表矩阵大小 n 和 m。

接下来 n 行，每行一个长度为 m 的只含字符 0 到 9 的字符串，代表这个 n \times m 的矩阵。

输出格式

一行一个整数代表细胞个数。

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

对于 100% 的数据，保证 1 <=n,m <=100。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
PII temppair;
queue<PII> q;

int Map[105][105],mark[105][105];
int n,m;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

bool pd(int x,int y)
{
	if(Map[x][y]==0)  //在本题中0是非细胞数字 
		return false;
	if(x<1||x>n||y<1||y>m) //越界检测
		return false;
	if(mark[x][y]==1) //已经去过的标记检测
		return false;
	return true;
}
void bfs()
{
	while(!q.empty())  
	{
		temppair=q.front(); //取队首元素
		q.pop(); //删除第一个元素
		for(int i=0;i<4;i++)
		{
			int nowx=temppair.first+dx[i];
			int nowy=temppair.second+dy[i];
			if(pd(nowx,nowy))
			{
				q.push({nowx,{nowy}}); //如果是细胞数字，并且没有越界，就把这个位置压入队列
				mark[nowx][nowy]=1; //并且做上标记
			}
		}
	}
}

int main()
{
	int cnt=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%1d",&Map[i][j]);  //！！！特别注意！！！ scanf可以控制输入的数字位数，比如这里%1d就是输入1位数，题目给的数字都是没有空格的
						
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(Map[i][j]!=0&&mark[i][j]!=1) //从左上角开始依次遍历
			{
				mark[i][j]=1;
				q.push({i,j});
				bfs();
				cnt++;
			}
		}
	cout<<cnt;
	return 0;
}

马的遍历

题目描述

有一个 n * m 的棋盘，在某个点 $(x, y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n, m, x, y。

输出格式

一个 n * m的矩阵，代表马到达某个点最少要走几步（不能到达则输出 -1）。

样例 #1

样例输入 #1

3 3 1 1

样例输出 #1

0    3    2    
3    -1   1    
2    1    4

代码

#include <bits/stdc++.h>
using namespace std;
#define N 500
typedef pair<int,int> PII;
PII temp;
queue<PII> q;
int dx[8]={1,2,2,1,-1,-2,-2,-1};  //马走日
int dy[8]={-2,-1,1,2,2,1,-1,-2};
int n,m,x2,y2;  //行 列 起x 起y 
long long Map[N][N]={0},done[N][N]={0};
int len;  //用以判断是否结束了这次扩张
bool pd(int x,int y)
{
	if(x<1||x>n||y<1||y>m)
		return false;
	if(done[x][y]==1)
		return false;
	return true;
}
void bfs()
{
	int step=1;
	while(!q.empty())
	{
		temp=q.front();
		q.pop();
		for(int i=0;i<8;i++)
		{
			int nowx=dx[i]+temp.first;
			int nowy=dy[i]+temp.second;
			if(pd(nowx,nowy))
			{
				Map[nowx][nowy]=step;
				done[nowx][nowy]=1;
				q.push({nowx,nowy});
			}
		}
		len--;
		if(len==0)
		{
			step++;	
			len=q.size();
		}	
	}
}
int main()
{
	cin>>n>>m>>x2>>y2;
	q.push({x2,y2});
	done[x2][y2]=1;
	bfs();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(Map[i][j]==0 && done[i][j]==0)
				Map[i][j]=-1;
			printf("%-5lld",Map[i][j]);
		}
		cout<<'\n';
	}	
	return 0;
	
}