hdu 2612

直接以两个人为起点进行BFS..然后标记，最短到当前这点的最短时间。最后求到 某个KFC最短的时间。

下面是 AC代码：
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<queue> 
using namespace std; 
const int MAX = 210; 
char map[MAX][MAX]; 
int n,m; 
int dir [4][2] ={{1,0},{0,1},{-1,0},{0,-1}}; 
struct node{ 
    int x,y; 
    int time; 
}s_pos; 
bool cheak(int x,int y){ 
    if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]!='#') return true ; 
    return false; 
} 
void bfs(int x,int y,int vis[210][210]){ 
    s_pos.x=x,s_pos.y=y; 
    s_pos.time=0; 
    queue<node > q; 
    q.push(s_pos); 
    vis[x][y]=0; 
    while(!q.empty()){ 
        node now = q.front(); q.pop(); 
        for(int i=0;i<4;i++){ 
            node next = now; 
            next.x+=dir[i][0],  next.y+=dir[i][1]; next.time=now.time+11; 
            if(cheak(next.x,next.y)&&vis[next.x][next.y]>vis[now.x][now.y]+11){ 
                vis[next.x][next.y]=vis[now.x][now.y]+11; 
 
                q.push(next); 
 
            } 
 
 
        } 
 
 
    } 
 
} 
int main(){ 
    int y_vis[MAX][MAX]; 
    int m_vis[MAX][MAX]; 
    while(cin>>n>>m){ 
        int s1_x,s1_y,s2_x,s2_y; 
        for(int i=0;i<n;i++)   scanf("%s",&map[i]); 
        for(int i=0;i<n;i++) for(int j=0;j<m;j++){ 
             m_vis[i][j]=y_vis[i][j]=1000000009; 
            if(map[i][j]=='Y')   s1_x=i,s1_y=j; 
            if(map[i][j]=='M')   s2_x=i,s2_y=j; 
        } 
        bfs(s1_x,s1_y,y_vis);  bfs(s2_x,s2_y,m_vis); 
 
//         for(int i=0;i<n;i++){ for(int j=0;j<m;j++) 
//             cout<<m_vis[i][j]<<" "; 
//             cout<<endl; 
//         } 
 
        int ans=0x7fffffff; 
        for(int i=0;i<n;i++) for(int j=0;j<m;j++) 
          if(map[i][j]=='@'&&ans>m_vis[i][j]+y_vis[i][j]) ans=m_vis[i][j]+y_vis[i][j]; 
 
          cout<<ans<<endl; 
    } 
    return 0; 
 
} 

补充：软件开发 , C++ ,

上一个：poj 2192 记忆化&dfs
下一个：IOCP加Windows线程池打造高伸缩性高性能的服务器应用