BFS(最短路+路径打印) POJ 3984 迷宫问题-白红宇

BFS(最短路+路径打印) POJ 3984 迷宫问题
阅读量：5276 次
发布时间：2019-06-14
本文共 2316 字，大约阅读时间需要 7 分钟。
1 /* 2     BFS：额，这题的数据范围太小了。但是重点是最短路的求法和输出路径的写法。 3         dir数组记录是当前点的上一个点是从哪个方向过来的，搜索+，那么回溯- 4 */ 5 /************************************************ 6 Author        :Running_Time 7 Created Time  :2015-8-4 9:02:06 8 File Name     :POJ_3984.cpp 9 ************************************************/10 11 #include 
     
      12 #include 
      
       13 #include 
       
        14 #include 
        
         15 #include 
         
          16 #include 
          
           17 #include 
           
            18 #include 
            
             19 #include 
             
              20 #include 
              
               21 #include 
               
                22 #include 
                
                 23 #include 
                 24 #include 
                  
                   25 #include 
                   
                    26 #include 
                    
                     27 #include 
                     
                      28 using namespace std;29 30 #define lson l, mid, rt << 131 #define rson mid + 1, r, rt << 1 | 132 typedef long long ll;33 const int MAXN = 10;34 const int INF = 0x3f3f3f3f;35 const int MOD = 1e9 + 7;36 int a[MAXN][MAXN];37 bool vis[MAXN][MAXN];38 int dir[MAXN][MAXN];39 int step[MAXN][MAXN];40 int dx[4] = {-1, 1, 0, 0};41 int dy[4] = { 0, 0, -1, 1};42 int n = 4, m = 4;43 44 bool judge(int x, int y) {45 if (x < 0 || x > n || y < 0 || y > m || a[x][y] == 1) return false;46 return true;47 }48 49 void print_path(void) {50 int x = n, y = m; vector
                      
                       
                         > ans;51 while (dir[x][y] != -1) {52 ans.push_back (make_pair (x, y));53 int px = x, py = y;54 x -= dx[dir[px][py]]; y -= dy[dir[px][py]];55 }56 int sz = (int) ans.size ();57 printf ("(0, 0)\n");58 for (int i=sz-1; i>=0; --i) {59 printf ("(%d, %d)\n", ans[i].first, ans[i].second);60 }61 }62 63 void BFS(void) {64 memset (vis, false, sizeof (vis));65 memset (step, INF, sizeof (step));66 memset (dir, -1, sizeof (dir));67 queue
                        
                         
                           > Q; Q.push (make_pair (0, 0)); vis[0][0] = true;68 step[0][0] = 0;69 while (!Q.empty ()) {70 int x = Q.front ().first, y = Q.front ().second; Q.pop ();71 for (int i=0; i<4; ++i) {72 int tx = x + dx[i], ty = y + dy[i];73 if (!judge (tx, ty)) continue;74 if (vis[tx][ty] && step[tx][ty] <= step[x][y] + 1) continue;75 if (tx == n && ty == m) {76 dir[tx][ty] = i; print_path (); return ;77 }78 dir[tx][ty] = i; step[tx][ty] = step[x][y] + 1;79 Q.push (make_pair (tx, ty)); vis[tx][ty] = true;80 }81 }82 }83 84 int main(void) { //POJ 3984 迷宫问题85 for (int i=0; i<5; ++i) {86 for (int j=0; j<5; ++j) {87 scanf ("%d", &a[i][j]);88 }89 }90 BFS ();91 92 return 0;93 }
转载于:https://www.cnblogs.com/Running-Time/p/4703136.html
你可能感兴趣的文章