dis[dx][dy] = dis[temp.x][temp.y]+1;
当时第一次看这到这个公式的时候反应是DP(我真是好久没做DP了)
后来发现原来这就是bfs的精髓
#include <iostream>
#include <cstring>
#include <queue>
#define INF 0x7fffffff
using namespace std;
int n,m;
char G[207][207];
int dir[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
struct pos{
int x,y;
};
int dis_1[207][207];
int dis_2[207][207];
bool judge(int x,int y)
{
if(x>=1&& x<=n && y>=1 && y<=m && G[x][y]!=‘#‘)
return true;
else return false;
}
void bfs(int a,int b,int vis[207][207],int dis[207][207])
{
vis[a][b] = 1;
queue<pos> q;
pos s;
s.x = a;
s.y = b;
q.push(s);
while(!q.empty())
{
pos temp = q.front();
q.pop();
for(int i = 0;i <= 3;i++)
{
int dx = temp.x+dir[i][0];
int dy = temp.y+dir[i][1];
if(!vis[dx][dy] && judge(dx,dy)) {
vis[dx][dy] = 1;
dis[dx][dy] = dis[temp.x][temp.y]+1;
pos n;
n.x = dx;
n.y = dy;
q.push(n);
}
}
}
}
int main()
{
while(cin>>n>>m)
{
int x1,y1,x2,y2;
int vis_1[207][207];
int vis_2[207][207];
for(int i = 1;i <= n;i++)
cin>>G[i]+1;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++) {
if(G[i][j] == ‘Y‘)
{
x1 = i;
y1 = j;
}
if(G[i][j] == ‘M‘)
{
x2 = i;
y2 = j;
}
}
memset(dis_1,0,sizeof(dis_1));
memset(dis_2,0,sizeof(dis_2));
memset(vis_1,0,sizeof(vis_1));
memset(vis_2,0,sizeof(vis_2));
bfs(x1,y1,vis_1,dis_1);
bfs(x2,y2,vis_2,dis_2);
int ans = INF;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
if(G[i][j] == ‘@‘ && vis_1[i][j] && vis_2[i][j])
ans = dis_1[i][j]+dis_2[i][j]<ans?dis_1[i][j]+dis_2[i][j]:ans;
cout<<ans*11<<endl;
}
return 0;
}
原文:http://www.cnblogs.com/immortal-worm/p/5133046.html