题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2612
BFS搜索 目标地 并记录下来 之后再判断两段路程之和
代码:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <ctype.h>
#include <iomanip>
#include <queue>
#include <stdlib.h>
using namespace std; #define INF 0x3f3f3f3f
#define N 220
#define M 220
int n,m;
char mp[N][M];
int vis1[N][M],vis2[N][M];
int ans1[N][M],ans2[N][M];
int dx[]={,,,-};
int dy[]={,-,,}; struct node
{
int x,y;
int t;
}; node g1,g2;
void getMp()
{
for(int i=; i<n; i++){
for(int j=; j<m; j++){
cin>>mp[i][j];
if(mp[i][j]=='Y'){
g1.x=i;
g1.y=j;
g1.t=;
vis1[i][j]=;
}
if(mp[i][j]=='M'){
g2.x=i;
g2.y=j;
g2.t=;
vis2[i][j]=;
}
}
}
} void bfs1()
{
queue<node> q;
while(!q.empty())
q.pop();
q.push(g1);
while(!q.empty()){
node f1;
f1=q.front();
q.pop();
for(int i=; i<; i++){
node f2;
f2.x=f1.x+dx[i];
f2.y=f1.y+dy[i];
f2.t=f1.t;
if(<=f2.x&&f2.x<n&&<=f2.y&&f2.y<m&&!vis1[f2.x][f2.y]&&mp[f2.x][f2.y]!='#'){
f2.t++;
if(mp[f2.x][f2.y]=='@'){
ans1[f2.x][f2.y]=f2.t;
}
vis1[f2.x][f2.y]=;
q.push(f2);
}
}
}
} void bfs2()
{
queue<node> q;
while(!q.empty())
q.pop();
q.push(g2);
while(!q.empty()){
node f1;
f1=q.front();
q.pop();
for(int i=; i<; i++){
node f2;
f2.x=f1.x+dx[i];
f2.y=f1.y+dy[i];
f2.t=f1.t;
if(<=f2.x&&f2.x<n&&<=f2.y&&f2.y<m&&!vis2[f2.x][f2.y]&&mp[f2.x][f2.y]!='#'){
f2.t++;
if(mp[f2.x][f2.y]=='@'){
ans2[f2.x][f2.y]=f2.t;
}
vis2[f2.x][f2.y]=;
q.push(f2);
}
}
}
} int main()
{
while(~scanf("%d %d",&n,&m)){
memset(ans1,-,sizeof(ans1));
memset(ans2,-,sizeof(ans2));
memset(vis1,,sizeof(vis1));
memset(vis2,,sizeof(vis2));
getMp();
bfs1();
bfs2();
int min=INF;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
{
if(ans1[i][j]+ans2[i][j]<min&&ans1[i][j]+ans2[i][j]>)
{
min=ans1[i][j]+ans2[i][j];
}
}
printf("%d\n",min*);
}
}