BFS
主要解决两类问题
1.从a出发是否存在到达b的路径
2.从a出发到b的最短路径
数据20以内dfs可能行。。。推荐bfs
大概就是对于一个点 一层一层访问周围的点（类似于子节点的子节点）
整体思路：
起始 扩散 终止

需要队列的原因：需要一层一层遍历 相邻节点的访问顺序需要确定
即使得先遍历到的节点先被存储 再按照存储先后顺序取出来遍历其子节点 综上所述队列符合

两道热身题

[洛谷1716离开中山路] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N]; //存地图
int dist[N][N];
typedef pair<int,int> PII;
queue<PII> s;
int n,x1,y11,x2,y2=0;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1}; 

int bfs(int x,int y)
{
	memset(dist,-1,sizeof(dist));
	s.push({x,y});
	dist[x][y]=0;
	while(!s.empty())
	{
		auto t=s.front();
		s.pop(); //第一个再删掉 
		
		for(int i=0;i<4;i++)
		{
			int a=t.first+dx[i];
			int b=t.second+dy[i];
			
			if(a<1 ||a>n || b<1 || b>n) continue;
			if(dist[a][b]>0) continue;
			if(g[a][b]!=0) continue;
			s.push({a,b});
			dist[a][b]=dist[t.first][t.second]+1;
		}

	}
	return dist[x2][y2];	
 } 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			char c;
			cin>>c;
			g[i][j]=c-'0';
		}
	}	
	cin>>x1>>y11>>x2>>y2;
	int res=bfs(x1,y11);
	cout<<res;
	return 0;
}

如果想要求路径 那么定义一个数组 bfs中每一次移动的时候存一下移动前的下标
从终点开始推

[洛谷1443马的遍历] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N]; //存地图
int dist[N][N];
typedef pair<int,int> PII;

int n,x1,y11,x2,y2=0;
PII q[N*N];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1}; 

int bfs(int x,int y)
{
	memset(dist,-1,sizeof(dist));
	int tt=-1;
	int hh=0;
	q[++tt]={x,y}; //其实这里可以将hh tt初始化为0 因为一开始就插了个数了
	dist[x][y]=0;
	while(hh<=tt)
	{   
	   	auto t = q[hh]; //auto t=s.front();
		hh++;         //s.pop();  这里可以写成auto tt=q[hh++]
		for(int i=0;i<4;i++)
		{
			int a=t.first+dx[i];
			int b=t.second+dy[i];
			
			if(a<1 ||a>n || b<1 || b>n) continue;
			if(dist[a][b]>0) continue;
			if(g[a][b]!=0) continue;
			q[++tt]={a,b};
			dist[a][b]=dist[t.first][t.second]+1;
			if(dist[x2][y2]>0) return dist[x2][y2];
		}

	}
	return dist[x2][y2];	
 } 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			char c;
			cin>>c;
			g[i][j]=c-'0';
		}
	}
	cin>>x1>>y11>>x2>>y2;
	int res=bfs(x1,y11);
	cout<<res;
	return 0;
}

多源bfs 好好感受一下
关键就是一开始就把感染源放队列里 这样就保证了同时性

[洛谷1332血色先锋队] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
typedef pair <int,int> PII;
PII q[510*510];
int dist[510][510];

int dx[]={0,0,1,-1};
int dy[]={-1,1,0,0};

int tt=-1,hh=0;

void bfs()
{
	while(hh<=tt)//不为空 
	{
		auto t=q[hh++]; //取队头 再弹出队头
		for(int i=0;i<4;i++)
		{
			int a=t.first+dx[i];
			int b=t.second+dy[i];
			if(a>n || a<1 || b>m || b<1) continue;
			if(dist[a][b]>=0) continue;
			dist[a][b]=dist[t.first][t.second]+1;
			q[++tt]={a,b};
		 } 
	}
		
}

int main()
{
	cin>>n>>m>>a>>b;
	
	memset(dist,-1,sizeof(dist));
	for(int i=0;i<a;i++)
	{
		int x0,y0;
		cin>>x0>>y0;
		q[++tt]={x0,y0};
		dist[x0][y0]=0;
	}
	bfs();
	while(b--)
	{
		int x1,y1;
		cin>>x1>>y1;
		cout<<dist[x1][y1]<<endl;
	}
	return 0;
 }

这题跟dfs连通块有点像 但是是反着来的

[洛谷1162填涂颜色] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
int n;
int g[35][35];
bool st[35][35];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
typedef pair<int,int> PII;
PII q[35*35];

void bfs(int x1,int y1)
{
	q[0]={x1,y1};
	int hh=0;
	int tt=0;
	while(hh<=tt)
	{
		auto t=q[hh++]; //取队头 弹出队头
		for(int i=0;i<4;i++)
		{
			int a=t.first+dx[i];
			int b=t.second+dy[i];
			if(g[a][b]==1) continue;
			if(a<0 || b<0 || a>n+1 || b>n+1 ) continue;
			if(st[a][b]) continue;
			st[a][b]=true;
			q[++tt]={a,b};
		 } 
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cin>>g[i][j];
	}
	
	bfs(0,0);
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(!st[i][j] && g[i][j]==0) g[i][j]=2;	
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cout<<g[i][j]<<" ";
		cout<<endl;
    }
    

	return 0;
}

这道题有些细节需要注意
1.初始化 fire存的是最早的陨石时间 所以可以初始化为0x3f
2.边界问题 因为陨石可以落到边界上 所以往外延伸一圈才是边界
3.时间的比较 需要逻辑清晰

[洛谷2895] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
int m;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

typedef pair<int,int> PII;

#define x first
#define y second
PII q[310*310];
bool st[310][310];
int dist[310][310];
int fire[310][310];
int bfs(int x1,int y1)
{
	memset(dist,-1,sizeof(dist));
	dist[x1][y1]=0;
	q[0]={x1,y1};
	int hh=0,tt=0;
	while(hh<=tt)
	{
		auto t=q[hh++];
		for(int i=0;i<4;i++)
		{
			int a=t.x+dx[i];
			int b=t.y+dy[i];
			if(a<0 || b<0 ) continue;
			if(dist[a][b]>0) continue;
			if(dist[t.x][t.y]+1>=fire[a][b]) continue;
			q[++tt]={a,b};
			dist[a][b]=dist[t.x][t.y]+1;
			q[++tt]={a,b};
			if(fire[a][b]>1e9) return dist[a][b];
		}
	}
	return -1;
}


int main()
{
	cin>>m;
	memset(fire,0x3f,sizeof fire);
	while(m--)
	{
		int x2,y2,t;
		cin>>x2>>y2>>t;
		fire[x2][y2]=min(t,fire[x2][y2]);
		for(int i=0;i<4;i++)
		{
			int a=x2+dx[i];
			int b=y2+dy[i];
			if(a<0 || a>301 || b<0 || b>301) continue;
			fire[a][b]=min(t,fire[a][b]);
		 } 
	}
	int res=bfs(0,0);
	cout<<res<<endl; 
	return 0;
}

这道题就是一个二分加bfs的结合
注意的问题
1.本题行是m 列是n
2.队列数组需要开够大
3. 二分板子需要记忆清楚

[洛谷2658] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std; 
int h[510][510],flag[510][510];
int x3,y3,ans,cnt1,m,n;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool st[510][510];
#define x first
#define y second

typedef pair<int,int> PII;
PII q[510*510];

bool check(int mid1)
{
	//cout<<x1<<" "<<y1<<endl;
	q[0]={x3,y3};
	st[x3][y3]=true;
	int cnt2=1; //统计经过的路标个数 
	int hh=0;
	int tt=0;
	while(hh<=tt)
	{
		
		auto t=q[hh++];
		for(int i=0;i<4;i++)
		{
			int a=t.x+dx[i];
			int b=t.y+dy[i];
			//cout<<t.x<<" "<<t.y<<endl;
			if(a<1 || a>m || b<1 || b>n) continue;
			if(abs(h[t.x][t.y]-h[a][b])>mid1) continue;
			if(st[a][b]==true) continue;
			

			q[++tt]={a,b};
			st[a][b]=true;
			
			if(flag[a][b]==1)
			{
				cnt2++;
				//cout<<cnt1<<" "<<cnt2<<endl;
				if(cnt2==cnt1) return true;
			}
		}
	}
	return false;	
}

int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++) cin>>h[i][j];
	}
	
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>flag[i][j];
			if(flag[i][j]==1) cnt1++;
		}
	}
	
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(flag[i][j]==1)
			{
				x3=i;
				y3=j;
				//cout<<x1<<" "<<y1<<endl;
				break;
			}
		}
	}
	//cout<<x1<<" "<<y1;
	int l=-1;
	int r=1e9+10; //找最少的 左边界
	while(l<=r)
	{
		//cout<<ans<<endl;
		memset(q,0,sizeof(q));
		memset(st,false,sizeof(st));
		int mid=(l+r)/2;
		//cout<<mid<<endl;
	
		if(check(mid))
		{
			ans=mid;
			r=mid-1;
			
		}
		else l=mid+1;
	 }

	cout<<ans<<endl;
	return 0;
}