hdu 1242 找到朋友最短的时间 (BFS+优先队列)

找到朋友的最短时间

Sample Input
7 8
#.#####. //#不能走 a起点 x守卫 r朋友
#.a#..r. //r可能不止一个
#..#x...
..#..#.#
#...##..
.#......
........

Sample Output
13

bfs+优先队列

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <queue>
 5 using namespace std;
 6 
 7 int n, m;
 8 char map[205][205];
 9 int sx, sy;
10 bool flag;
11 
12 struct node
13 {
14     int x , y , step ;
15     bool operator <(const node &t) const
16     {
17         return step > t.step ;
18     }
19 };
20 
21 int dx[] = {0,0,1,-1} ;
22 int dy[] = {1,-1,0,0} ;
23 
24 void bfs()
25 {
26     node now , t ;
27     int i , fx ,fy ;
28     priority_queue<node> q ;
29     now.x = sx ;
30     now.y = sy ;
31     now.step = 0 ;
32     q.push(now) ;
33     map[sx][sy] = '#' ;
34     while(!q.empty())
35     {
36         now = q.top() ;
37         q.pop() ;
38         for (i = 0 ; i < 4 ; i++)
39         {
40             fx = now.x + dx[i] ;
41             fy = now.y + dy[i] ;
42             if (fx<0 || fy<0 || fx >=n || fy >=m ||map[fx][fy] == '#')
43                 continue ;
44             if (map[fx][fy] == 'r')
45             {
46                 printf("%d
" , now.step+1) ;
47                 flag = 1 ;
48                 return ;
49             }
50             if (map[fx][fy] == 'x')
51             {
52                 t.x = fx ;
53                 t.y = fy ;
54                 t.step = now.step + 2 ;
55                 q.push(t) ;
56             }
57             else
58             {
59                 t.x = fx ;
60                 t.y = fy ;
61                 t.step = now.step + 1 ;
62                 q.push(t) ;
63             }
64             map[fx][fy] = '#' ;
65 
66         }
67     }
68 
69 
70 }
71 
72 int main()
73 {
74   //  freopen("in.txt","r",stdin) ;
75     while (scanf("%d %d" , &n , &m) !=EOF)
76     {
77         int i , j ;
78         for (i = 0 ; i < n ; i++)
79         {
80             for (j = 0 ; j < m ; j++)
81             {
82                 cin>>map[i][j] ;
83                 if (map[i][j] == 'a')
84                 {
85                     sx = i ;
86                     sy = j ;
87                 }
88             }
89         }
90         flag = 0 ;
91         bfs() ;
92         if (!flag)
93             printf("Poor ANGEL has to stay in the prison all his life.
") ;
94     }
95 
96     return 0 ;
97 }

View Code

dfs

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 char map[220][220] ;
 9 bool visit[220][220] ;
10 
11 int n , m ;
12 int MIN ;
13 
14 
15 
16 void dfs(int x , int y , int sum)
17 {
18     if (x<0 || y<0 || x>= n || y>= m)
19         return ;
20     if (map[x][y] == '#')
21         return ;
22     if (sum >= MIN)
23         return ;
24     if (visit[x][y] == 1)
25         return ;
26     if (map[x][y] == 'r')
27     {
28         if (sum < MIN)
29             MIN = sum ;
30         return ;
31     }
32     if (map[x][y] == 'x')
33         sum++ ;
34     visit[x][y] = 1 ;
35     dfs(x+1,y,sum+1) ;
36     dfs(x-1,y,sum+1) ;
37     dfs(x,y+1,sum+1) ;
38     dfs(x,y-1,sum+1) ;
39     visit[x][y] = 0 ;
40 }
41 
42 int main()
43 {
44    // freopen("in.txt","r",stdin) ;
45 
46 
47    while (scanf("%d %d" , &n , &m) !=EOF)
48    {
49        if (n == 0 && m == 0)
50           break ;
51        memset(visit ,0 ,sizeof(visit)) ;
52        int i , j ;
53        int bx , by ;
54        int sum = 0 ;
55 
56        for (i = 0 ; i < n ; i++)
57        {
58            for (j = 0 ; j < m ; j++)
59           {
60               cin>>map[i][j];
61               if (map[i][j] == 'a')
62               {
63                   bx = i ;
64                   by = j ;
65    
66               }
67           }
68 
69        }
70        
71 
72        
73 
74        MIN = INT_MAX ;
75        dfs(bx,by,sum) ;
76        if (MIN != INT_MAX)
77          printf("%d
" , MIN) ;
78        else
79          printf("Poor ANGEL has to stay in the prison all his life.
") ;
80 
81    }
82 
83     return 0;
84 }

View Code