题意：给你5*5的矩阵，要求你从左上角（0,0）走到右下角（4,4）的最短路径。
题解：用对路径用bf，我们记住每个点的前驱，输出用dfs
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cctype> 5 #include <cmath> 6 #include <time.h> 7 #include <string> 8 #include <map> 9 #include <stack> 10 #include <set> 11 #include <queue> 12 #include <vector> 13 #include <algorithm> 14 #include <iostream> 15 using namespace std; 16 typedef long long ll; 17 #define PI acos( -1.0 ) 18 typedef pair<int, int> 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) " ); 30 return; 31 } 32 output( dx[x][y], dy[x][y] ); 33 printf( "(%d, %d) ", x, y ); 34 } 35 36 void bfs() 37 { 38 queue <P> 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 }