제목 출처:https://vjudge.net/contest/159739#problem/N[제의] Y와 M은 같은 @시에 가서 커피를 마시며 데이트를 하려고 합니다. 가장 짧은 시간을 부탁합니다.[생각] Y와 M은 각각 한 번씩 광범위하게 검색하고 전체 그림을 검색하며 적당히 가지를 잘라서 @점까지의 시간을 기록한다. [코드]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int INF=1e9;
typedef long long LL;
int n,m;
int w[204][204];
char area[204][204];
bool vis[204][204];
int d[4][2]= {{0,1},{0,-1},{-1,0},{1,0}};
struct pp
{
int x,y,t;
} q1,q2,q3,q4;
bool check(int x,int y)
{
if(vis[x][y]||area[x][y]=='#'||x<0||x>=n||y<0||y>=m)
return 0;
return 1;
}
void init()
{
for(int i=0;ifor(int j=0;j0);
}
void bfs()
{
int num=0,num1=0,num2=0;
queue q;
for(int i=0; iscanf("%s",area[i]);
for(int j=0; jif(area[i][j]=='Y')
{
q1.x=i;
q1.y=j;
q1.t=0;
vis[i][j]=1;
}
else if(area[i][j]=='M')
{
q3.x=i;
q3.y=j;
q3.t=0;
}
else if(area[i][j]=='@')
num++;
}
}
q.push(q1);
while(!q.empty())
{
q1=q.front();
q.pop();
for(int i=0; i<4; i++)
{
q2.x=q1.x+d[i][0];
q2.y=q1.y+d[i][1];
if(check(q2.x,q2.y))
{
q2.t=q1.t+1;
vis[q2.x][q2.y]=1;
q.push(q2);
if(area[q2.x][q2.y]=='@')
{
num1++;
w[q2.x][q2.y]=q2.t;
if(num1==num)
break;
}
}
}
}
while(!q.empty())
q.pop();
mem(vis,0);
vis[q3.x][q3.y]=1;
q.push(q3);
while(!q.empty())
{
q3=q.front();
q.pop();
for(int i=0; i<4; i++)
{
q4.x=q3.x+d[i][0];
q4.y=q3.y+d[i][1];
if(check(q4.x,q4.y))
{
q4.t=q3.t+1;
vis[q4.x][q4.y]=1;
q.push(q4);
if(area[q4.x][q4.y]=='@')
{
num2++;
w[q4.x][q4.y]+=q4.t;
if(num2==num)
break;
}
}
}
}
}
void print()
{
int minn=1e9;
for(int i=0;ifor(int j=0;jif(area[i][j]=='@')
{
if(minn>w[i][j])
minn=w[i][j];
}
}
}
printf("%d
",minn*11);
}
int main()
{
while(~scanf("%d%d%*c",&n,&m))
{
init();
bfs();
print();
}
}