学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2612

题目大意：两个人，他们想在某家KCF见面，要求他们到这家KCF的时间花费最少。

解题思路：这道题是一道求迷宫最短路径问题，要用BFS搜索下搜索到第一条的路径就是最短路径，我们要分别以两个人为起点，对图进行两次的BFS，分别求出各自到KCF得最短距离，之后比较多个KCF的距离，输出最短的距离就好。

#include <string><br /> #include <iostream><br /> #include <deque><br /> using namespace std;<br /> #define size 201</p> <p>/*节点信息*/<br /> struct node<br /> {<br /> int x,y,count;<br /> };</p> <p>char s[size][size];<br /> int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};<br /> int m,n;<br /> int Yx,Yy,Mx,My;/*两个人的坐标*/<br /> int dist1[size][size],dist2[size][size];/*两个人到任意一点的距离*/<br /> bool visited[size][size];<br /> deque<node>Q;</p> <p>void BFS(node p,int dist[][size])<br /> {<br /> int i;<br /> node q;<br /> memset(visited,0,sizeof(visited));<br /> memset(dist,0,sizeof(dist));<br /> Q.push_front(p);<br /> while (!Q.empty())<br /> {<br /> p = Q.front();<br /> Q.pop_front();<br /> /*四个方向搜索入队*/<br /> for (i=0;i<4;i++)<br /> {<br /> q.x = p.x+dir[i][0];<br /> q.y = p.y+dir[i][1];<br /> q.count = p.count+1;<br /> if (q.x>=0&&q.y>=0&&q.x<m&&q.y<n&&s[q.x][q.y]!='#'&&!visited[q.x][q.y])<br /> {<br /> visited[q.x][q.y] = 1;<br /> dist[q.x][q.y] = q.count;<br /> Q.push_back(q);<br /> }<br /> }<br /> }<br /> }</p> <p>int main()<br /> {<br /> int i,j,min;<br /> node p;<br /> /*freopen("d://1.txt","r",stdin);*/<br /> while (scanf("%d%d",&m,&n)!=EOF)<br /> {<br /> for (i=0;i<m;i++)<br /> {<br /> for (j=0;j<n;j++)<br /> {<br /> cin>>s[i][j];<br /> if(s[i][j]=='Y')<br /> Yx=i,Yy=j;<br /> else if(s[i][j]=='M')<br /> Mx = i,My = j;<br /> }<br /> }</p> <p> min = 999999999;<br /> p.x = Yx,p.y=Yy,p.count=0;<br /> BFS(p,dist1);/*求Yifenfei到其他各个点的距离*/<br /> p.x = Mx,p.y=My,p.count=0;<br /> BFS(p,dist2);/*求Merceki到其他各个点的距离*/</p> <p> for (i=0;i<m;i++)<br /> for (j=0;j<n;j++)<br /> if (s[i][j]=='@')/*是KFC，开始计算距离总和*/<br /> if (dist1[i][j]!=0&&dist2[i][j]!=0)<br /> if(dist1[i][j]+dist2[i][j]<min)/*比较求距离的最小值*/<br /> min = dist1[i][j]+dist2[i][j];</p> <p> printf("%d/n",min*11);<br /> }<br /> return 0;<br /> }