HDU 2612 Find a way bfs 难度:1

http://acm.hdu.edu.cn/showproblem.php?pid=2612

bfs两次就可将两个人到达所有kfc的时间求出,取两人时间之和最短的即可,这个有点不符合实情,题目应该出两人最大时间最小才对

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int inf=0x3fffffff;
char maz[300][301];
int n,m;
int mdp[300][300],ydp[300][300];

queue<int> que;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
bool in(int x,int y){
        return x>=0&&x<n&&y>=0&&y<m;
}
void bfs(int sx,int sy,int dp[300][300]){
        dp[sx][sy]=0;
        que.push(sx*300+sy);
        while(!que.empty()){
                int x=que.front()/300,y=que.front()%300;que.pop();
                for(int i=0;i<4;i++){
                        int tx=x+dx[i],ty=y+dy[i];
                        if(in(tx,ty)&&maz[tx][ty]!='#'&&dp[tx][ty]>dp[x][y]+1){
                                dp[tx][ty]=dp[x][y]+1;
                                que.push(tx*300+ty);
                        }
                }
        }
}

int main(){
        while(scanf("%d%d",&n,&m)==2){
                for(int i=0;i<n;i++){
                        scanf("%s",maz[i]);
                }
                for(int i=0;i<n;i++){
                        for(int j=0;j<m;j++){
                                mdp[i][j]=ydp[i][j]=inf;
                        }
                }
                for(int i=0;i<n;i++){
                        for(int j=0;j<m;j++){
                                if(maz[i][j]=='M'){
                                        bfs(i,j,mdp);
                                }
                                else if(maz[i][j]=='Y'){
                                        bfs(i,j,ydp);
                                }
                        }
                }
                int ans=inf;
                for(int i=0;i<n;i++){
                        for(int j=0;j<m;j++){
                                if(maz[i][j]=='@'){
                                        ans=min(ans,mdp[i][j]+ydp[i][j]);
                                }
                        }
                }
                printf("%d
",ans*11);
        }
        return 0;
}