HDU/HDOJ 2612 양 방향 BFS 방법 찾기

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2612
사고:두 개의 출발점 에서 출발 하여 여러 개의 종점 이 있 습 니 다.두 개의 출발점 에서 동시에 도착 할 수 있 는 종점 이 가지 고 있 는 최소 시간 을 구하 고 두 개의 배열 을 열 어 각각 두 개의 출발점 을 저장 하여 모든 종점 에 도착 할 때 마지막 으로 두 개 를 저장 합 니 다.
배열 의 시간 을 합 쳐 가장 작은 조 를 구 하려 면 반드시 대응 해 야 한다.왜냐하면 종점 은 반드시 동시에 도착 해 야 하기 때문이다.

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <queue>
using namespace std;
struct node{
	int x,y,step;
}a[1010];
node p,q;
int n,m,sx1,sy1,sx2,sy2,ans1[1010],ans2[1010],ans[1010];
int mmin,cnt;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};  
char maze[205][205];
bool visit[205][205];
int judge(int x,int y){
	for(int i=1;i<cnt;i++)
	{
		if(x==a[i].x&&y==a[i].y)return i;
	}
	return 0;
}
void bfs1(int x,int y){
	memset(ans,0,sizeof(ans));
	memset(ans1,-1,sizeof(ans1));
	memset(visit,0,sizeof(visit));
	queue<node> Q;
	p.x=x;
	p.y=y;
	p.step=0;
	Q.push(p);
	visit[p.x][p.y]=1;
	while(!Q.empty())
	{
		p=Q.front();
		Q.pop();
		int num=judge(p.x,p.y);
		if(num){
			ans[num]=p.step;
			visit[p.x][p.y]=1;
		}
		for(int i=0;i<4;i++)
		{
			q.x=p.x+dir[i][0];
			q.y=p.y+dir[i][1];
			q.step=p.step+1;
			if(q.x<0||q.x>=n||q.y<0||q.y>=m)continue;
			if(visit[q.x][q.y])continue;
			if(maze[q.x][q.y]=='#')continue;
			Q.push(q);
			visit[q.x][q.y]=1;
		}
	}
	for(int i=1;i<cnt;i++){
		if(ans[i])ans1[i]=ans[i];
	}
	
}
void bfs2(int x,int y){
	memset(ans,0,sizeof(ans));
	memset(ans2,-1,sizeof(ans2));
	memset(visit,0,sizeof(visit));
	queue<node> Q;
	p.x=x;
	p.y=y;
	p.step=0;
	Q.push(p);
	visit[p.x][p.y]=1;
	while(!Q.empty())
	{
		p=Q.front();
		Q.pop();
		int num=judge(p.x,p.y);
		if(num){
			ans[num]=p.step;
			visit[p.x][p.y]=1;
		}
		for(int i=0;i<4;i++)
		{
			q.x=p.x+dir[i][0];
			q.y=p.y+dir[i][1];
			q.step=p.step+1;
			if(q.x<0||q.x>=n||q.y<0||q.y>=m)continue;
			if(visit[q.x][q.y])continue;
			if(maze[q.x][q.y]=='#')continue;
			Q.push(q);
			visit[q.x][q.y]=1;
		}
	}
	for(int i=1;i<cnt;i++){
		if(ans[i])ans2[i]=ans[i];
	}
}
int main()
{
	//ifstream fin;
	//fin.open("data1.txt");
	
	while(cin>>n>>m)
	{
		cnt=1;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++){
				cin>>maze[i][j];
				if(maze[i][j]=='Y'){
					sx1=i;
					sy1=j;
				}
				if(maze[i][j]=='M'){
					sx2=i;
					sy2=j;
				}
				if(maze[i][j]=='@'){
					a[cnt].x=i;
					a[cnt++].y=j;
				}
			}
			mmin=999999;
			bfs1(sx1,sy1);
			bfs2(sx2,sy2);
			for(int i=1;i<cnt;i++)
			{
				if(ans1[i]!=-1&&ans2[i]!=-1){
					int tsum=ans1[i]+ans2[i];
					if(mmin>tsum)mmin=tsum;
				}
			}
			cout<<mmin*11<<endl;
	}
	return 0;

}