hdoj 2612 find a way (两次bfs)

Posted by 111qqz on Saturday, July 25, 2015

TOC


Find a way

****Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6221 Accepted Submission(s): 2070
**

**

Problem Description

Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei's home is at the countryside, but Merceki's home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.
Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.

**

**

Input

The input contains multiple test cases.
Each test case include, first two integers n, m. (2<=n,m<=200).
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’ express Merceki initial position.
‘#’ forbid road;
‘.’ Road.
‘@’ KCF

**

**

Output

For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.

**

**

Sample Input

4 4
Y.#@
….
.#..
@..M
4 4
Y.#@
….
.#..
@#.M
5 5
Y..@.
.#…
.#…
@..M.
#…#

**

**

Sample Output

66
88
66

**

**

Author

yifenfei

**

**

Source

奋斗的年代

一开始写成了让对没个肯德基店做一次bfs,会TLE

之后发现然对两个人分别做一次bfs就行

只是遇到肯德基店的 时候,因为不能确定这个是否是做优的,所以不return,继续搜下去.

/*************************************************************************
    > File Name: code/2015summer/searching/N.cpp
    > Author: 111qqz
    > Email: rkz2013@126.com 
    > Created Time: 2015年07月25日 星期六 13时54分49秒
 ************************************************************************/

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#define y0 abc111qqz
#define y1 hust111qqz
#define yn hez111qqz
#define j1 cute111qqz
#define tm crazy111qqz
#define lr dying111qqz
using namespace std;
#define REP(i, n) for (int i=0;i<int(n);++i)  
typedef long long LL;
typedef unsigned long long ULL;
const int N= 2E2+5;
char st[N][N];
int n,m;
int d[N][N];
int dd[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
struct node
{
    int x,y;
}kfc[N];
node M,Y;
void bfs(int xo,int yo)
{
    memset(d,-1,sizeof(d));
    queue<int>x;
    queue<int>y;
    x.push(xo);
    y.push(yo);
    d[xo][yo]=0;
    while (!x.empty())
    {
       int px=x.front();x.pop();
       int py=y.front();y.pop();
       for ( int i = 0 ; i < 4 ; i++ )
       {
         int nx = px+dx[i];
         int ny = py+dy[i];
         if (nx>=0&&nx<n&&ny>=0&&ny<m&&d[nx][ny]==-1&&st[nx][ny]!='#')
         {
             d[nx][ny]=d[px][py]+1;
             x.push(nx);
             y.push(ny);
         }
       }

    }
  //  cout<<"res1:"<<res<<endl;
}
void bfs2(int xo,int yo)
{
    memset(dd,-1,sizeof(dd));
    queue<int>x;
    queue<int>y;
    x.push(xo);
    y.push(yo);
    dd[xo][yo]=0;
    while (!x.empty())
    {
      int px = x.front();x.pop();
      int py =y.front();y.pop();
      for ( int i = 0 ;  i <4 ; i++ )
      {
        int nx = px +dx[i];
        int ny = py +dy[i];
        if (nx>=0&&nx<n&&ny>=0&&ny<m&&dd[nx][ny]==-1&&st[nx][ny]!='#')
        {
            dd[nx][ny]= dd[px][py]+1;
            x.push(nx);
            y.push(ny);
        }
      }
    }

}




int main()
{
    while (scanf("%d %d",&n,&m)!=EOF)
    {
      for ( int i = 0 ; i < n ; i++ )
      {
        cin>>st[i];
      }
      int k = 0;
      for ( int i = 0 ;  i < n ; i++)
      {
        for ( int j = 0 ; j < m ; j++ )
        {
            if (st[i][j]=='Y')
            {
              Y.x=i;
              Y.y=j;
            }
            if (st[i][j]=='M')
            {
              M.x=i;
              M.y=j;
            }
        }
      }
      bfs(Y.x,Y.y);
      bfs2(M.x,M.y);
      int ans = 99999999;
      for ( int i =  0 ; i < n ; i++ )
      {
        for ( int j = 0 ;  j < m ; j++ )
        {
            if (st[i][j]=='@')
            {
             // cout<<d[i][j]<<"  "<<dd[i][j]<<endl;
              if (d[i][j]==-1||dd[i][j]==-1) continue;
              ans = min(ans,d[i][j]+dd[i][j]);
            }
        }
      }
	  
      cout<<ans*11<<endl;
    }
  
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付