HDU/HDOJ 2612 양 방향 BFS 방법 찾기
사고:두 개의 출발점 에서 출발 하여 여러 개의 종점 이 있 습 니 다.두 개의 출발점 에서 동시에 도착 할 수 있 는 종점 이 가지 고 있 는 최소 시간 을 구하 고 두 개의 배열 을 열 어 각각 두 개의 출발점 을 저장 하여 모든 종점 에 도착 할 때 마지막 으로 두 개 를 저장 합 니 다.
배열 의 시간 을 합 쳐 가장 작은 조 를 구 하려 면 반드시 대응 해 야 한다.왜냐하면 종점 은 반드시 동시에 도착 해 야 하기 때문이다.
#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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
제1 6 장 파일 에서 텍스트 검색 도구: grep 명령 과 egrep 명령제1 6 장 파일 에서 텍스트 검색 도구: grep 명령 과 egrep 명령 옵션 grep 명령 파일 에서 단 어 를 검색 하면 명령 은 "match pattern"을 포함 하 는 텍스트 줄 을 되 돌려 줍 니 다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.