bfs——带地板类题

BFS

BFS（广度优先搜索）是一种逐层扩展的搜索算法。从起点开始，先访问所有距离为 1 的节点，再访问所有距离为 2 的节点，以此类推。

核心特点：第一次到达某个节点时，一定是最短路径（边权全为 1 时）。

基本框架

1、普通

queue<Node> q; q.push(起点); vis[起点] = 1; while (!q.empty()) { auto cur = q.front(); q.pop(); for (每个相邻节点 nxt) { if (nxt 合法 && !vis[nxt]) { vis[nxt] = 1; dis[nxt] = dis[cur] + 1; q.push(nxt); } } }

2、0/1bfs

用于：边权只有 0 和 1 的最短路。
做法：用双端队列（deque）代替普通队列。
走权值为 0 的边：从队首插入
走权值为 1 的边：从队尾插入

deque<Node> dq; dq.push_front(起点); while (!dq.empty()) { auto cur = dq.front(); dq.pop_front(); for (每条边) { if (边权 == 0 && dis[nxt] > dis[cur]) { dis[nxt] = dis[cur]; dq.push_front(nxt); } if (边权 == 1 && dis[nxt] > dis[cur] + 1) { dis[nxt] = dis[cur] + 1; dq.push_back(nxt); } } }

3、优先队列 BFS（Dijkstra）

用于：边权为任意非负整数的最短路。
做法：用优先队列（小根堆）代替普通队列，按距离排序。

priority_queue<Node> pq; pq.push({起点, 0}); while (!pq.empty()) { auto [cur, d] = pq.top(); pq.pop(); if (d > dis[cur]) continue; for (每条边) { if (dis[nxt] > dis[cur] + w) { dis[nxt] = dis[cur] + w; pq.push({nxt, dis[nxt]}); } } }

4、双向 BFS

用于：起点和终点都已知，且搜索空间极大。
做法：从起点和终点同时开始 BFS，两个搜索相遇时结束。

// 单词接龙、八数码、迷宫等 int bfs(string start, string end) { if (start == end) return 0; queue<string> q1, q2; // 两个方向的队列 unordered_map<string, int> d1, d2; // 两个方向的距离 q1.push(start); d1[start] = 0; q2.push(end); d2[end] = 0; while (!q1.empty() && !q2.empty()) { // 每次扩展较小的队列（优化） int t; if (q1.size() <= q2.size()) { t = extend(q1, d1, d2); // 从起点方向扩展一步 } else { t = extend(q2, d2, d1); // 从终点方向扩展一步 } if (t != -1) return t; // 相遇了，返回总距离 } return -1; // 无法到达 } int extend(queue<string>& q, unordered_map<string, int>& d_cur, // 当前方向的距离 unordered_map<string, int>& d_other) // 对面方向的距离 { int sz = q.size(); while (sz--) { // 扩展一层 string cur = q.front(); q.pop(); for (每个相邻状态 nxt) { if (d_cur.count(nxt)) continue; // 当前方向已经访问过 // 如果对面方向访问过，说明相遇 if (d_other.count(nxt)) { return d_cur[cur] + 1 + d_other[nxt]; } d_cur[nxt] = d_cur[cur] + 1; q.push(nxt); } } return -1; // 还没相遇 }

范题

www.lanqiao.cn/problems/21594/learning/?page=1&first_category_id=1
定义dist[o][x][y][p]状态,表示技能剩余o次到达(x,y)时下一步的环境是p的最少代价,因为计算完代价,p就+1了,符合结尾条件。
使用技能是为了更好的符合环境，是为了少扣血，相当与一次免费改变环境为col的值的机会，所以将每个可以改变的节点都试一次，肯定可以找到最优路径不遗漏。

#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define endl '\n' using namespace std; //包含原地 int dx[]={1,0,-1,0,0}; int dy[]={0,1,0,-1,0}; struct node{ int x,y,p,cost,o;//x,y,当前环境,代价,是否有技能 bool operator<(const node&o)const{//优先队列代价小的优先 return cost>o.cost; } }; int bfs(vector<string>map,vector<vector<int>>col,int n,int m,int P){ int sx,sy; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(map[i][j]=='S')sx=i,sy=j; } } //四维数组定义 vector<vector<vector<vector<int>>>>dist(2,vector<vector<vector<int>>>(n,vector<vector<int>>(m,vector<int>(P,1e9)))); dist[1][sx][sy][0]=0;//初始未使用技能,p=0 priority_queue<node>q; q.push({sx,sy,0,0,1}); while(q.size()){ auto [x,y,p,cost,o]=q.top();q.pop(); if(map[x][y]=='T')return cost;//优先队列一定不能早返回 for(int i=0;i<5;i++){//遍历5种移动方向 int xx=x+dx[i],yy=y+dy[i]; if(xx<0||xx>=n||yy<0||yy>=m)continue; if(map[xx][yy]=='#')continue; int c=(p==col[xx][yy])?0:1;//计算这步移动是否有代价 int np=(p+1)%P;//新环境值 if(dist[o][xx][yy][np]>cost+c){//不使用技能 dist[o][xx][yy][np]=cost+c; q.push({xx,yy,np,cost+c,o}); } if(o==1){//使用技能 np=(col[xx][yy]+1)%P; if(dist[0][xx][yy][np]>cost+1){ dist[0][xx][yy][np]=cost+1; q.push({xx,yy,np,cost+1,0}); } } } } return -1;//未找到 } void solve() { int n,m,P;cin>>n>>m>>P; vector<string>map(n); for(int i=0;i<n;i++){ cin>>map[i]; } vector<vector<int>>col(n,vector<int>(m)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>col[i][j]; } } cout<<bfs(map,col,n,m,P); } int main() { ios::sync_with_stdio(false), cin.tie(0); int t = 1;//cin>>t; while (t--)solve(); return 0; }