宽度优先搜索BFS

宽度优先搜索的过程中每次都会从当前点向外扩展⼀层所以会具有⼀个最短路的特性。因此宽搜不仅能搜到所有的状态⽽且还能找出起始状态距离某个状态的最⼩步数。但是前提条件是每次扩展的代价都是1 或者都是相同的数。宽搜常常被⽤于解决边权为1的最短路问题。1.P1443 马的遍历解题思路先把第一次可以走到的点加入到队列里再依次把第一次可以走到的点当成起点再次找下一次可以到达的点加入到队列直到队列中无元素后遍历结束代码#includeiostream#includecstring#includequeueusingnamespacestd;typedefpairint,intPII;constintN410;intdist[N][N];intdx[]{2,1,-1,-2,-2,-1,1,2};intdy[]{1,2,2,1,-1,-2,-2,-1};intn,m,x,y;voidbfs(){//初始化起点memset(dist,-1,sizeofdist);queuePIIq;q.push({x,y});dist[x][y]0;while(q.size()){intaq.front().first;intbq.front().second;q.pop();for(inti0;i8;i){inta1adx[i];intb1bdy[i];if(a11||a1n||b11||b1m)continue;if(dist[a1][b1]!-1)continue;//加入q.push({a1,b1});dist[a1][b1]dist[a][b]1;}}}intmain(){cinnmxy;bfs();for(inti1;in;i){for(intj1;jm;j){coutdist[i][j] ;}coutendl;}return0;}2 kotori和迷宫解题思路确定起点利用BFS依次遍历第一次遍历出来的一定是最小值代码#includeiostream#includequeue#includecstringusingnamespacestd;typedefpairint,intPII;constintN31;intdist[N][N];chara[N][N];intdx[]{0,0,1,-1};intdy[]{1,-1,0,0};intn,m;intret0;voidbfs(intx,inty){memset(dist,-1,sizeofdist);queuePIIq;q.push({x,y});dist[x][y]0;while(q.size()){autoiq.front();intx1i.first;inty1i.second;q.pop();for(inti0;i4;i){intx2x1dx[i];inty2y1dy[i];if(x21||x2n||y21||y2m)continue;if(a[x2][y2]*)continue;if(dist[x2][y2]!-1)continue;if(a[x2][y2]e){ret;dist[x2][y2]dist[x1][y1]1;continue;}q.push({x2,y2});dist[x2][y2]dist[x1][y1]1;}}}intmain(){cinnm;intx,y;for(inti1;in;i){for(intj1;jm;j){cina[i][j];if(a[i][j]k){xi;yj;}}}bfs(x,y);intnum1e9;for(inti1;in;i){for(intj1;jm;j){if(a[i][j]edist[i][j]!-1){nummin(num,dist[i][j]);}}}if(ret0)cout-1endl;elsecoutret num;;return0;}3.P1588 [USACO07OPEN] Catch That Cow S解题思路BFS暴搜会出现相同的值直接剪枝代码#includeiostream#includequeue#includecstringusingnamespacestd;constintN1e510;intdist[N];intT,n,m;voidbfs(){queueintq;q.push(n);dist[n]0;while(q.size()){intiq.front();q.pop();intai1;intbi-1;intci*2;if(aNdist[a]-1){dist[a]dist[i]1;q.push(a);}if(b0dist[b]-1){dist[b]dist[i]1;q.push(b);}if(cNdist[c]-1){dist[c]dist[i]1;q.push(c);}if(am||bm||cm){return;}}}intmain(){cinT;while(T--){memset(dist,-1,sizeofdist);cinnm;bfs();coutdist[m]endl;}return0;}