bfs——带地板类题

BFSBFS广度优先搜索是一种逐层扩展的搜索算法。从起点开始先访问所有距离为 1 的节点再访问所有距离为 2 的节点以此类推。核心特点第一次到达某个节点时一定是最短路径边权全为 1 时。基本框架1、普通queueNode 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 的边从队尾插入dequeNode 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、优先队列 BFSDijkstra用于边权为任意非负整数的最短路。做法用优先队列小根堆代替普通队列按距离排序。priority_queueNode 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; queuestring q1, q2; // 两个方向的队列 unordered_mapstring, 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(queuestring q, unordered_mapstring, int d_cur, // 当前方向的距离 unordered_mapstring, 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/?page1first_category_id1定义dist[o][x][y][p]状态,表示技能剩余o次到达(x,y)时下一步的环境是p的最少代价,因为计算完代价,p就1了,符合结尾条件。使用技能是为了更好的符合环境是为了少扣血相当与一次免费改变环境为col的值的机会所以将每个可以改变的节点都试一次肯定可以找到最优路径不遗漏。#includebits/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 nodeo)const{//优先队列代价小的优先 return costo.cost; } }; int bfs(vectorstringmap,vectorvectorintcol,int n,int m,int P){ int sx,sy; for(int i0;in;i){ for(int j0;jm;j){ if(map[i][j]S)sxi,syj; } } //四维数组定义 vectorvectorvectorvectorintdist(2,vectorvectorvectorint(n,vectorvectorint(m,vectorint(P,1e9)))); dist[1][sx][sy][0]0;//初始未使用技能,p0 priority_queuenodeq; 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 i0;i5;i){//遍历5种移动方向 int xxxdx[i],yyydy[i]; if(xx0||xxn||yy0||yym)continue; if(map[xx][yy]#)continue; int c(pcol[xx][yy])?0:1;//计算这步移动是否有代价 int np(p1)%P;//新环境值 if(dist[o][xx][yy][np]costc){//不使用技能 dist[o][xx][yy][np]costc; q.push({xx,yy,np,costc,o}); } if(o1){//使用技能 np(col[xx][yy]1)%P; if(dist[0][xx][yy][np]cost1){ dist[0][xx][yy][np]cost1; q.push({xx,yy,np,cost1,0}); } } } } return -1;//未找到 } void solve() { int n,m,P;cinnmP; vectorstringmap(n); for(int i0;in;i){ cinmap[i]; } vectorvectorintcol(n,vectorint(m)); for(int i0;in;i){ for(int j0;jm;j){ cincol[i][j]; } } coutbfs(map,col,n,m,P); } int main() { ios::sync_with_stdio(false), cin.tie(0); int t 1;//cint; while (t--)solve(); return 0; }