BFS

BFS 全称是 Breadth First Search，中文名是广度优先搜索。

是图上最基础、最重要的搜索算法之一。

所谓广度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗，我们通常用队列来实现。

例题：

#include<bits/stdc++.h>
using namespace std;

int n, m; 
int g[110][110], vis[110][110], dist[110][110]; // g存图,vis标记x,y是否走过，dist记录起点到x,y的最短距离
int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0}; // 方向数组

bool check(int nx, int ny) 
{
  // 没有越界，没有来过，且不是墙
  if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && g[nx][ny] == 0) 
    return true;
  return false;
}

void bfs()
{
	/*
	1.起点入队
	2.当队列不为空，弹出队头元素，并拓展队头
	3.重复2，直到队列为空
	4.输出答案
	*/
	queue<pair<int,int>> q;
	q.push({1,1});
	vis[1][1] = 1; // 起点标记
	dist[1][1] = 0; // 初始化距离
	while (q.size())
	{
		auto t = q.front(); q.pop();
		int x = t.first, y = t.second;
		if (x == n && y == m) return;
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i], ny = y + dy[i];
			if (check(nx, ny))
			{
				vis[nx][ny] = 1;
				q.push({nx, ny});
				dist[nx][ny] = dist[x][y] + 1;
			}
		}
	}
}

int main()
{
	memset(dist, 0x3f, sizeof dist); // 初始化极大值
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j++)
			cin >> g[i][j];
	bfs(); 
	cout << dist[n][m];
	
	return 0;
}

DFS

DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况。

我们通常用递归和栈来实现。

例题：

#include<bits/stdc++.h>
using namespace std;

int n, m; 
int g[110][110], vis[110][110], dist[110][110]; // g存图,vis标记x,y是否走过，dist记录起点到x,y的最短距离
int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0}; // 方向数组

bool check(int nx, int ny) 
{
  // 没有越界，没有来过，且不是墙
  if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && g[nx][ny] == 0) 
    return true;
  return false;
}

void dfs(int x, int y)
{
	if (x == n && y == m) // 边界判定
	{
		return;
	}
	for (int i = 0; i < 4; i++) // 循环4个方向
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (check(nx, ny) && dist[x][y] + 1 < dist[nx][ny]) // 可行性判定并进一步搜索
		{
			vis[nx][ny] = 1; // 标记
			dist[nx][ny] = dist[x][y] + 1; // 更新最短路
			dfs(nx, ny); // 递归搜索
			vis[nx][ny] = 0; // 回溯
		}
	}
}

int main()
{
	memset(dist, 0x3f, sizeof dist); // 初始化极大值
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j++)
			cin >> g[i][j];
	vis[1][1] = 1; // 起点标记
	dist[1][1] = 0; // 初始化距离
	dfs(1,1); 
	cout << dist[n][m];
	
	return 0;
}