***求最短路徑，然后再輸出路徑，

BFS+路徑輸出***

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <stack> #include <queue> #include <cmath>using namespace std; typedef long long LL; #define oo 0x3f3f3f3f #define N 100int maps[10][10]; int dir[4][2]= {{1,0}, {0,1}, {-1,0}, {0,-1}}, vis[N][N], step[N][N];struct node {int x, y, s;} a, b;int k;void BFS(int x, int y) {k=0;queue<node> q;a.x=x;a.y=y;a.s=0;q.push(a);vis[0][0]=1;step[0][0]=0;k++;while(!q.empty()){a=q.front();q.pop();for(int i=0; i<4; i++){b.x=a.x+dir[i][0];b.y=a.y+dir[i][1];if(b.x>=0&&b.x<5&&b.y>=0&&b.y<5&&maps[b.x][b.y]==0&&!vis[b.x][b.y]){b.s=a.s+1;q.push(b);step[b.x][b.y]=b.s;vis[b.x][b.y]=1;} }} }void put(int x, int y) {if(x==0 && y==0){printf("(%d, %d)\n", x, y);return ;}for(int i=0; i<4; i++){int nx=x+dir[i][0];int ny=y+dir[i][1];if(nx>=0 && nx<5 && ny>=0 && ny<5 && step[x][y]==step[nx][ny]+1 && vis[nx][ny]){put(nx, ny);printf("(%d, %d)\n", x, y);}} }int main() {for(int i=0; i<5; i++)for(int j=0; j<5; j++)scanf("%d", &maps[i][j]);memset(vis, 0, sizeof(vis));memset(step, 0, sizeof(step));BFS(0, 0);put(4, 4);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/9968jie/p/5666006.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的广搜 广搜 poj 3984的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。