<题目链接>
题目大意：
两个人分别从地图中的Y 和 M出发，要共同在 @ 处会面（@不止有一处），问这两个人所走距离和的最小值是多少。
解题分析：
就是对这两个点分别进行一次BFS，求出它们到每一个 @ 点的最短距离，然后距离和最小的即为所求（图上一步相当于 11）。此题有坑，必须判断两个人是否都能够走到那个@点，如果不能走到，那么那个距离和应该作废。
#include<iostream>
#include<queue>
#include<algorithm>
#include<memory.h>
#include<utility>
using namespace std;
typedef pair<int,int> P;
const int MAX=;
int dir[][]={,,,,-,,,-};
char maze[MAX][MAX];
int visa[MAX][MAX],visb[MAX][MAX];
int n,m;
void bfs(int x,int y,int vis[][MAX])
{
queue<P>q;
q.push(P(x,y));
while(!q.empty())
{
P p=q.front();
q.pop();
for(int i=;i<;i++) {
int nx=p.first+dir[i][],ny=p.second+dir[i][];
if(nx>=&&ny>=&&nx<n&&ny<m&&maze[nx][ny]!='#'&&vis[nx][ny]==) {
vis[nx][ny]=vis[p.first][p.second]+;
q.push(P(nx,ny));
}
}
}
} int main()
{
while(~scanf("%d%d",&n,&m))
{
int a,b,c,d;
memset(visa,,sizeof(visa));
memset(visb,,sizeof(visb));
for(int i=;i<n;i++){
scanf("%s",&maze[i]);
for(int j=;j<m;j++) {
if(maze[i][j]=='Y') {
a=i,b=j;
}
if(maze[i][j]=='M') {
c=i,d=j;
}
}
}
bfs(a,b,visa);
bfs(c,d,visb);
int mini=0x3f3f3f3f;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(maze[i][j]=='@'&&visa[i][j]+visb[i][j]!=) //未到达的KFC
mini=min(mini,visa[i][j]+visb[i][j]);
cout<<mini<<endl;
}
return ;
}
这是我的代码，WA了，但是不知道为什么，先记录下来。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std; const int maxn=+;
#define INF 0x3f3f3f3f int n,m;
char mpa[maxn][maxn];
int vis[maxn][maxn];
int dis[maxn];
int arrive[maxn]; int dir[][]={,,,,-,,,-}; struct NODE{
int x,y;
NODE(int a=,int b=){
x=a,y=b;
}
};
vector<NODE>v; struct node{
int x,y;
int step;
node(int a=,int b=,int c=):x(a),y(b),step(c){}
}; void bfs(node ital){
memset(vis,,sizeof(vis));
queue<node>q;
q.push(ital);
vis[ital.x][ital.y]=;
while(!q.empty()){
node now=q.front();
q.pop();
if(mpa[now.x][now.y]=='@'){
for(int i=;i<v.size();i++){
if(v[i].x==now.x&&v[i].y==now.y){
dis[i]+=now.step;
arrive[i]++;
}
}
}
for(int k=;k<;k++){
int xx=now.x+dir[k][];
int yy=now.y+dir[k][];
if(xx<||xx>n||yy<||yy>m||vis[xx][yy]||mpa[xx][yy]=='#')continue;
if(mpa[xx][yy]=='Y'||mpa[xx][yy]=='M')continue;
vis[xx][yy]=;
q.push(node(xx,yy,now.step+));
}
}
} int main(){
while(scanf("%d %d",&n,&m)!=EOF){
v.clear();
for(int i=;i<=n;i++){
scanf("%s",mpa[i]+);
for(int j=;j<=m;j++){
if(mpa[i][j]=='@'){
v.push_back(NODE(i,j)); //将全部 @单独地存到vector中，这样会给每一个@编号,方便查询
}
}
}
memset(arrive,,sizeof(arrive));
memset(dis,,sizeof(dis));
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mpa[i][j]=='Y'||mpa[i][j]=='M'){
bfs(node(i,j,));
}
}
}
int mx=INF;
for(int i=;i<v.size();i++){
if(arrive[i]!=)dis[i]=INF; //如果这个KFC不是两个人都能到达，那么求出来的dis无效，所以将其设为INF
mx=min(mx,dis[i]);
}
printf("%d\n",mx*);
}
return ;
}
2018-08-29