hdoj 2612 find a way (两次bfs)


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,继续搜下去.

  1
  2
  3   
  4   /*************************************************************************
  5   	> File Name: code/2015summer/searching/N.cpp
  6   	> Author: 111qqz
  7   	> Email: rkz2013@126.com 
  8   	> Created Time: 2015年07月25日 星期六 13时54分49秒
  9    ************************************************************************/
 10   
 11   #include<iostream>
 12   #include<iomanip>
 13   #include<cstdio>
 14   #include<algorithm>
 15   #include<cmath>
 16   #include<cstring>
 17   #include<string>
 18   #include<map>
 19   #include<set>
 20   #include<queue>
 21   #include<vector>
 22   #include<stack>
 23   #define y0 abc111qqz
 24   #define y1 hust111qqz
 25   #define yn hez111qqz
 26   #define j1 cute111qqz
 27   #define tm crazy111qqz
 28   #define lr dying111qqz
 29   using namespace std;
 30   #define REP(i, n) for (int i=0;i<int(n);++i)  
 31   typedef long long LL;
 32   typedef unsigned long long ULL;
 33   const int N= 2E2+5;
 34   char st[N][N];
 35   int n,m;
 36   int d[N][N];
 37   int dd[N][N];
 38   int dx[4]={0,0,-1,1};
 39   int dy[4]={1,-1,0,0};
 40   struct node
 41   {
 42       int x,y;
 43   }kfc[N];
 44   node M,Y;
 45   void bfs(int xo,int yo)
 46   {
 47       memset(d,-1,sizeof(d));
 48       queue<int>x;
 49       queue<int>y;
 50       x.push(xo);
 51       y.push(yo);
 52       d[xo][yo]=0;
 53       while (!x.empty())
 54       {
 55   	   int px=x.front();x.pop();
 56   	   int py=y.front();y.pop();
 57   	   for ( int i = 0 ; i < 4 ; i++ )
 58   	   {
 59   		 int nx = px+dx[i];
 60   		 int ny = py+dy[i];
 61   		 if (nx>=0&&nx<n&&ny>=0&&ny<m&&d[nx][ny]==-1&&st[nx][ny]!='#')
 62   		 {
 63   	 	     d[nx][ny]=d[px][py]+1;
 64   		     x.push(nx);
 65   		     y.push(ny);
 66   		 }
 67   	   }
 68   
 69       }
 70     //  cout<<"res1:"<<res<<endl;
 71   }
 72   void bfs2(int xo,int yo)
 73   {
 74       memset(dd,-1,sizeof(dd));
 75       queue<int>x;
 76       queue<int>y;
 77       x.push(xo);
 78       y.push(yo);
 79       dd[xo][yo]=0;
 80       while (!x.empty())
 81       {
 82   	  int px = x.front();x.pop();
 83   	  int py =y.front();y.pop();
 84   	  for ( int i = 0 ;  i <4 ; i++ )
 85   	  {
 86   		int nx = px +dx[i];
 87   		int ny = py +dy[i];
 88   		if (nx>=0&&nx<n&&ny>=0&&ny<m&&dd[nx][ny]==-1&&st[nx][ny]!='#')
 89   		{
 90   		    dd[nx][ny]= dd[px][py]+1;
 91   		    x.push(nx);
 92   		    y.push(ny);
 93   		}
 94   	  }
 95       }
 96   
 97   }
 98   
 99   
100   
101   
102   int main()
103   {
104       while (scanf("%d %d",&n,&m)!=EOF)
105       {
106   	  for ( int i = 0 ; i < n ; i++ )
107   	  {
108   		cin>>st[i];
109   	  }
110   	  int k = 0;
111   	  for ( int i = 0 ;  i < n ; i++)
112   	  {
113   		for ( int j = 0 ; j < m ; j++ )
114   		{
115   		    if (st[i][j]=='Y')
116   		    {
117   			  Y.x=i;
118   	 		  Y.y=j;
119   		    }
120   		    if (st[i][j]=='M')
121   		    {
122   	 		  M.x=i;
123   			  M.y=j;
124   	 	    }
125   		}
126   	  }
127   	  bfs(Y.x,Y.y);
128   	  bfs2(M.x,M.y);
129   	  int ans = 99999999;
130   	  for ( int i =  0 ; i < n ; i++ )
131   	  {
132   		for ( int j = 0 ;  j < m ; j++ )
133   		{
134   		    if (st[i][j]=='@')
135   		    {
136   			 // cout<<d[i][j]<<"  "<<dd[i][j]<<endl;
137   			  if (d[i][j]==-1||dd[i][j]==-1) continue;
138   			  ans = min(ans,d[i][j]+dd[i][j]);
139   		    }
140   		}
141   	  }
142   	  
143   	  cout<<ans*11<<endl;
144       }
145     
146   	return 0;
147   }
148   
149
150