HDOJ 2612 Find a way【最短路双重bfs】

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2612

1、Y与M在KFC约定见面，在此之前不能见面，所以对于Y和M个人来说，M和Y所在的位置是不能走的
2、有一些KFC不能到达，步数为0，这个时候步数非常小但是不是正确答案，最后排除一下
3、步数计数方式：visY[xx][yy] = visY[x][y]+1;（父结点步数+1）

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<queue>
  6 using namespace std;
  7 const int MAXL = 205; // 矩阵最大宽度
  8 char maze[MAXL][MAXL]; // 迷宫
  9 int visY[MAXL][MAXL]; // 访问标记(Y到达坐标点所需步数)
 10 int visM[MAXL][MAXL]; // 访问标记(M到达坐标点所需步数)
 11 int n, m; // 迷宫的长和宽
 12 int dirx[4] = {1, 0, -1, 0};
 13 int diry[4] = {0, 1, 0, -1}; // 移动方向(下 右 上 左)
 14 typedef struct point{
 15     int x, y;
 16 }P; // 坐标
 17 queue<P> path; // 路径
 18 P Y, M;
 19 const int INF = 1000;
 20 
 21 void Output(){
 22     for(int i = 0; i < n; i++){
 23         for(int j = 0; j < m; j++){
 24             printf("%c", maze[i][j]);
 25         }
 26         printf("
");
 27     }
 28 }
 29 
 30 void Input(){
 31     memset(maze, 0, sizeof(maze));
 32     memset(visY, 0, sizeof(visY));
 33     memset(visM, 0, sizeof(visM));
 34     for(int i = 0; i < n; i++){
 35             scanf("%s", &maze[i]);
 36         }
 37     //Output();
 38 }
 39 
 40 bool go(int xx, int yy){
 41     if(xx >= 0 && xx < n && yy >= 0 && yy < m && (maze[xx][yy] == '.' || maze[xx][yy] == '@')){
 42         return true;
 43     }
 44     else
 45         return false;
 46 }
 47 
 48 void bfs(P start, char flag){
 49     P current, next;
 50     int x, y, xx, yy; // x,y是当前坐标 xx,yy是下一步的坐标
 51 
 52     path.push(start);
 53 
 54     while(!path.empty()){ // 如果队列不为空
 55         current = path.front();
 56         x = current.x;
 57         y = current.y;
 58         for(int i = 0; i < 4; i++){
 59             xx = x + dirx[i];
 60             yy = y + diry[i];
 61             if(flag == 'Y' && visY[xx][yy] == 0 && go(xx, yy)){
 62                 visY[xx][yy] = visY[x][y]+1;
 63                 next.x = xx;
 64                 next.y = yy;
 65                 path.push(next);
 66             }
 67             else if(flag == 'M' && visM[xx][yy] == 0 && go(xx, yy)){
 68                 visM[xx][yy] = visM[x][y]+1;
 69                 next.x = xx;
 70                 next.y = yy;
 71                 path.push(next);
 72             }
 73         }
 74         path.pop();
 75     }
 76 }
 77 
 78 //void OutputY(){
 79 //    for(int i = 0; i < n; i++){
 80 //        for(int j = 0; j < m; j++){
 81 //            printf("%d	", visY[i][j]);
 82 //        }
 83 //        printf("
");
 84 //    }
 85 //}
 86 //
 87 //void OutputM(){
 88 //    for(int i = 0; i < n; i++){
 89 //        for(int j = 0; j < m; j++){
 90 //            printf("%d	", visM[i][j]);
 91 //        }
 92 //        printf("
");
 93 //    }
 94 //}
 95 
 96 void Resolve(){
 97     for(int i = 0; i < n; i++){ // 找到Y & M 所在坐标
 98         for(int j = 0; j < m; j++){
 99             if(maze[i][j] == 'Y'){
100                 Y.x = i;
101                 Y.y = j;
102             }
103             if(maze[i][j] == 'M'){
104                 M.x = i;
105                 M.y = j;
106             }
107         }
108     }
109     bfs(Y, 'Y');
110     bfs(M, 'M');
111 //
112 //    printf("
");
113 //    OutputY();
114 //    printf("
");
115 //    OutputM();
116 //    printf("
");
117 
118     int minStep = INF;
119     for(int i = 0; i < n; i++){
120         for(int j = 0; j < m; j++){
121             if(maze[i][j] == '@'){
122                 if((visY[i][j] + visM[i][j] < minStep) && (visY[i][j] + visM[i][j] != 0)) minStep = visY[i][j] + visM[i][j];
123             }
124         }
125     }
126     printf("%d
", minStep * 11);
127 }
128 
129 int main(){
130     while(~scanf("%d%d", &n, &m)){
131         Input();
132         Resolve();
133     }
134 
135     return 0;
136 }

HDOJ 2612 Find a way【最短路 双重bfs】

HDOJ 2612 Find a way【最短路双重bfs】