这是一道稍微有点特殊的题,特殊之处在于它需要使用2次广搜。刚开始做的时候思路是把所有肯德基的位置记录下来,然后以每一个肯德基的位置为终点来bfs。。。。。。然后就TLE了OTZ。。。。。。后来发现只需要只需要用两次bfs,把整个地图走遍,如果走到的地方是肯德基,就记录此时的步数,然后两个最小值相加乘以11就行了。 代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <climits>
#pragma GCC optimize(2)
using namespace std;
int n,m;
const int maxn=205;
char nbo[maxn][maxn];
int kfc_dis1[maxn][maxn],kfc_dis2[maxn][maxn];
int yif[1][2],mer[1][2];
int dir[4][2]=<!--swig0-->;
int vis[maxn][maxn];
typedef struct{
int row;
int col;
int stp;
}pos;
bool check(pos xxx)
{
if((nbo[xxx.row][xxx.col]=='M')||(nbo[xxx.row][xxx.col]=='Y')||(nbo[xxx.row][xxx.col]=='#')||
(xxx.row>=n)||(xxx.row<0)||(xxx.col>=m)||(xxx.col<0)||(vis[xxx.row][xxx.col]==1))
return false;
return true;
}
int kcnt=0;
void bfs(int stx,int sty) //x为行,y为列
{
kcnt=0;
queue<pos> que;
pos now,next,sta;
sta.row=stx;sta.col=sty;sta.stp=0;
que.push(sta);
vis[stx][sty]=1;
memset(vis,0,sizeof(vis));
while(!que.empty())
{
now=que.front();
if(nbo[now.row][now.col]=='@')
kfc_dis2[now.row][now.col]=now.stp;
for(int i=0;i<4;i++)
{
next.row=now.row+dir[i][0];
next.col=now.col+dir[i][1];
if(check(next))
{
vis[next.row][next.col]=1;
next.stp=now.stp+1;
que.push(next);
}
}
que.pop();
}
return ;
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(nbo,0,sizeof(nbo));memset(vis,0,sizeof(vis));
memset(kfc_dis1,0,sizeof(kfc_dis1));memset(kfc_dis2,0,sizeof(kfc_dis2));
int cnt=0,step;
int i,j;
getchar();
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%c",&nbo[i][j]);
if(nbo[i][j]=='M') {mer[0][0]=i;mer[0][1]=j;}
if(nbo[i][j]=='Y') {yif[0][0]=i;yif[0][1]=j;}
}
getchar();
}
int ans=INT_MAX;
bfs(mer[0][0],mer[0][1]);
memcpy(kfc_dis1,kfc_dis2,sizeof(kfc_dis2)); //kfc_cnt1:mer到各个肯德基距离,kfc_cnt2:yif到各个肯德基距离
memset(kfc_dis2,0,sizeof(kfc_dis2));
bfs(yif[0][0],yif[0][1]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(ans>kfc_dis1[i][j]+kfc_dis2[i][j]&&kfc_dis1[i][j]&&kfc_dis2[i][j])
ans=kfc_dis1[i][j]+kfc_dis2[i][j];
printf("%d\n",ans*11);
}
return 0;
}
另外,在hdoj的讨论版里有人说Y和M不能走,但经过尝试,"Y和M可以走"以及“Y和M不可以走”这两种写法都是可以AC的。