POJ 3984-白红宇

POJ 3984

阅读量：5105 次

发布时间：2019-06-13

本文共 1609 字，大约阅读时间需要 5 分钟。

题意：给你5*5的矩阵，要求你从左上角（0,0）走到右下角（4,4）的最短路径。

题解：用对路径用bf，我们记住每个点的前驱，输出用dfs

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #include 
                  
                   14 #include 
                   
                    15 using namespace std;16 typedef long long ll;17 #define PI acos( -1.0 )18 typedef pair
                    
                      P;19 const double E = 1e-8;20 const int NO = 100 + 5;21 int a[10][10], dx[10][10], dy[10][10];22 int mark[10][10];23 int dir[][2] = { {-1,0}, { 1,0}, { 0,-1}, { 0,1} };24 25 void output( int x, int y )26 {27 if( x == 0 && y == 0 )28 {29 printf( "(0, 0)\n" );30 return;31 }32 output( dx[x][y], dy[x][y] );33 printf( "(%d, %d)\n", x, y );34 }35 36 void bfs()37 {38 queue 
                      q;39 memset( mark, 0, sizeof( mark ) );40 memset( dx, 0, sizeof( dx ) );41 memset( dy, 0, sizeof( dy ) );42 q.push( P( 0, 0 ) );43 dx[0][0] = dy[0][0] = -1;44 while( !q.empty() )45 {46 P t = q.front(); q.pop();47 if( t.first == 4 && t.second == 4 )48 {49 output( 4, 4 );50 return;51 }52 for( int i = 0; i < 5; ++i )53 {54 int xx = dir[i][0] + t.first;55 int yy = dir[i][1] + t.second;56 if( xx >= 0 && xx < 5 && yy >= 0 && yy < 5 && !mark[xx][yy] && a[xx][yy] == 0 )57 {58 mark[xx][yy] = 1;59 dx[xx][yy] = t.first;60 dy[xx][yy] = t.second;61 q.push( P( xx, yy ) );62 }63 }64 }65 }66 67 int main()68 {69 for( int i = 0; i < 5; ++i )70 for( int j = 0; j < 5;++j )71 scanf( "%d", &a[i][j] );72 bfs();73 return 0;74 }