首页 > 代码库 > hdu2612(bfs)

hdu2612(bfs)

 

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

题意:求2个点到任意一个KFC的距离之和,使其最小。

分析:由两个点出发分别两次bfs,求得到每个KFC的距离,再枚举每个KFC求得最小距离和即可。刚开始以为KFC不能通过,wa了一次,坑。。。

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010using namespace std;int n,m;char s[210][210];int vis[210][210];int step1[210][210],step2[210][210];struct node{    int x,y;};int dx[]={0,0,1,-1};int dy[]={1,-1,0,0};int judge(int x,int y){    return x>=0&&x<n&&y>=0&&y<m&&s[x][y]!=#;}void bfs(int x,int y,int flag){    queue<node>que;    memset(vis,0,sizeof(vis));    node cur,nxt;    cur.x=x;cur.y=y;    que.push(cur);    vis[x][y]=1;    while(!que.empty())    {        cur=que.front();que.pop();        int xx=cur.x,yy=cur.y;        for(int i=0;i<4;i++)        {            int a=xx+dx[i],b=yy+dy[i];            if(judge(a,b)&&!vis[a][b])            {                if(flag)                step1[a][b]=step1[xx][yy]+1;                else step2[a][b]=step2[xx][yy]+1;                vis[a][b]=1;                nxt.x=a,nxt.y=b;                que.push(nxt);            }        }    }}int main(){    int x,y,a,b;    while(scanf("%d%d",&n,&m)>0)    {        for(int i=0;i<n;i++)            scanf("%s",s[i]);        for(int i=0;i<n;i++)        for(int j=0;j<m;j++)        {            if(s[i][j]==Y)            {                x=i;y=j;            }            if(s[i][j]==M)            {                a=i;b=j;            }        }        memset(step1,0,sizeof(step1));        memset(step2,0,sizeof(step2));        bfs(x,y,0);bfs(a,b,1);        int ans=inf;        for(int i=0;i<n;i++)            for(int j=0;j<m;j++)        {            if(s[i][j]==@&&step1[i][j]&&step2[i][j])            {                ans=min(ans,step1[i][j]+step2[i][j]);            }        }        printf("%d\n",ans*11);    }}
View Code

 

hdu2612(bfs)