09.01总结

状态空间由状态和状态转移构成，这与图的顶点和边类似——状态对应顶点，转移对应边。我们可以通过顺序遍历下标来枚举一维序列中的所有元素，而在图中又如何枚举呢？若简单地按节点编号顺序访问，就无法体现节点间的关联性，所以需要采用特定的枚举顺序，比如在寻找两点间路径时沿着图的边进行枚举。本质上，对图的枚举方式就是搜索。

深度优先搜索（DFS）

DFS 采用深度优先的策略：访问节点时会优先沿着当前路径继续深入，直到无法继续时才回溯。实现时通常使用递归函数，在当前节点依次选择未访问的边继续搜索，完成所有可能路径的探索后回溯。为避免重复访问，需要记录已访问状态。值得注意的是，某些问题虽然不直接涉及图论，但通过建立状态空间模型并搜索虚拟图也能求解。实际实现时只需动态确定状态转移的相邻节点，无需麻烦地构建整个图结构。

广度优先搜索（BFS）

BFS 按照与起点距离由近及远的顺序访问节点。实现时使用队列存储待访问节点：每次取出队首节点（距离最近），检查其邻接节点并将未访问节点入队。得益于队列的先进先出（FIFO）特性，距离起点更近的节点会优先被处理。在无权图中，BFS 能确保首次访问某个节点时经过的路径必定是最短路径。

01 BFS

针对边权仅为 0 或 1 的特殊图，可采用双端队列优化：取出队首节点后，将 0 权边连接的节点插入队首，1 权边连接的节点插入队尾。这种处理方式既保持了队列中节点按距离排序的特性，又能确保 BFS “首次访问某个节点时经过的路径必定是最短路径” 的特性，同时将时间复杂度优化至 $O(n+m)$。该算法在特定场景下既保留了 BFS 的优势，又显著提升了效率。

例题 - 01 BFS

CF1063B - Labyrinth

#include<bits/stdc++.h>
using namespace std;
int n, m, ans, sx, sy, mol, mor, dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, c[2001][2001];
struct tmp{int x, y, mol, mor;
};
string a[2001];//我用的 string 存地图
deque <tmp> q;//经典的双端队列
void bfs(int x, int y, int mol, int mor){q.push_front({x, y, mol, mor});//四个状态while(!q.empty()){int x = q.front().x, y = q.front().y, mol = q.front().mol, mor = q.front().mor;q.pop_front();if(x < 1 || x > n || y < 1 || y > m || c[x][y] || mol < 0 || mor < 0 || a[x][y] == '*'){//越界了、有障碍、负数个左右限制或走过了就不要continue;}ans++;c[x][y] = 1;for(int i = 0;i <= 3;i++){int nx = x + dx[i], ny = y + dy[i];if(i == 0 || i == 2){//上下无需限制q.push_front({nx, ny, mol, mor});} else {q.push_back({nx, ny, mol - (i == 3 ? 1 : 0), mor - (i == 1 ? 1 : 0)});//左右走，需消耗限制}}}
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m >> sx >> sy >> mol >> mor;for(int i = 1;i <= n;i++){cin >> a[i];a[i] = '0' + a[i];//为方便计算，加上一个 0}bfs(sx, sy, mol, mor);cout << ans;
}

本题的要点就是将上下和左右分别转化成 0 权边和 1 权边，运用双端队列优化。