33DAI：批量导入三三文档

2026-05-20T18:24:04Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第91行：		第91行：
	[[Category:搜索]]		[[Category:搜索]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:20Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 广度优先搜索（BFS） ==

BFS 从起点出发，'''逐层向外扩展'''。使用队列实现，保证第一次访问到的路径是最短路径（边权为 <math>1</math> 时）。

=== 网格最短路 ===

<syntaxhighlight lang="cpp">
struct Node
{
int x, y, step;
};

int bfs(int sx, int sy, int tx, int ty)
{
queue<Node> q;
q.push({sx, sy, 0});
vis[sx][sy] = true;

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

while (!q.empty())
{
auto [x, y, step] = q.front();
q.pop();

if (x == tx && y == ty)
return step;

for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (vis[nx][ny] || g[nx][ny] == '#') continue;
vis[nx][ny] = true;
q.push({nx, ny, step + 1});
}
}
return -1; // 不可达
}
</syntaxhighlight>

=== BFS 求最少步数 ===

<syntaxhighlight lang="cpp">
// 从 start 到 target 的最少变化次数
queue<string> q;
map<string, int> dist;

q.push(start);
dist[start] = 0;

while (!q.empty())
{
string u = q.front();
q.pop();

if (u == target)
return dist[u];

for (string v : get_next(u))
{
if (!dist.count(v))
{
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
</syntaxhighlight>

=== 多源 BFS ===

将所有起点同时入队，即可求出到最近起点的距离：

<syntaxhighlight lang="cpp">
queue<pair<int, int>> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (g[i][j] == 'S') // 所有起点入队
{
q.push({i, j});
vis[i][j] = true;
dis[i][j] = 0;
}
// BFS 过程同上
</syntaxhighlight>

[[Category:搜索]]
[[Category:三三文档]]

10-搜索/02-广度优先搜索 - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档