hdu2612 Find a way(BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
const int N = 300;
char s[N][N],c[N][N];
int d[100000],p[100000];
int s1,s2,e1,e2;
#define INF 0x3f3f3f3f
struct node
{
  int a,b;
  int step;
  node(){}
  node(int a,int b,int c):a(a),b(b),step(c){}
};
node tmp,rmp;
int dir[][2] = {{1,0},{-1,0},{0,-1},{0,1}};  int n,m;
void bfs()
{
    queue<node> Q1,Q2;vector<int> v1,v2;
    Q1.push(tmp);
    while(Q1.size())//求出Y到@的最短路径
    {
        tmp = Q1.front();
        Q1.pop();
        int a = tmp.a,b = tmp.b,step = tmp.step;
        for(int i = 0;i<4;++i){
            int x = a + dir[i][0],y = b + dir[i][1];
            if(s[x][y]=='.'){
                s[x][y] = '#';
                Q1.push(node(x,y,step+1));
            }
            else if(s[x][y] == '@'){
                s[x][y] = '#';
                d[(x-1)*m + y] = (step+1)*11;//记录下来
                Q1.push(node(x,y,step+1));//别忘了放进队列！！！
                v1.push_back((x-1)*m + y);
            }
        }
    }
    Q2.push(rmp);
    while(Q2.size())
    {
        rmp = Q2.front();
        Q2.pop();
        int a = rmp.a,b = rmp.b,step = rmp.step;
        for(int i = 0;i<4;++i){
            int x = a + dir[i][0],y = b + dir[i][1];
            if(c[x][y]=='.'){
                c[x][y] = '#';
                Q2.push(node(x,y,step+1));
            }
            else if(c[x][y] == '@'){
                c[x][y] = '#';
                Q2.push(node(x,y,step+1));
                v2.push_back((x-1)*m + y);
                p[(x-1)*m + y] = (step+1)*11;
            }
        }
    }
    int MIN = INF;//以下求到@最短距离，因为有的@可能某个人到不了，所以初始化为 -1
    for(int i = 0;i < v1.size();++i){
        if(p[v1[i]]==-1) continue;
        MIN = min(p[v1[i]]+ d[v1[i]],MIN);
    }
    for(int i = 0;i < v2.size();++i){
        if(d[v2[i]]==-1) continue;
        MIN = min(p[v2[i]] + d[v2[i]],MIN);
    }
    cout<<MIN<<endl;


}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif 

    while(cin>>n>>m)
    {
        int cnt = 0;
        for(int i = 1;i <= n;++i)
        {
            for(int j= 1;j <= m; ++j)
            {
                cin>>s[i][j];
                c[i][j] = s[i][j];
                if(c[i][j] == 'Y') s1 = i,s2 = j;
                else if(c[i][j] == 'M') e1 = i,e2 = j;
            }
        }
            memset(d,-1,sizeof (d));
            memset(p,-1,sizeof(p));
            tmp.a = s1,tmp.b = s2,tmp.step = 0;
            rmp.a = e1,rmp.b = e2,rmp.step = 0;
            s[e1][e2] = '#';//对于Y来说，M相当于墙
            s[s1][s2] = '#';
            c[s1][s2] = '#';//对于M来说，Y相当于墙
            c[e1][e2] = '#';
            bfs();
    }
}