链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2612
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6718 Accepted Submission(s): 2236
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <queue> using namespace std; #define INF 0x3f3f3f3f #define N 210 struct node { int x, y, step; }; int n, m, a[N][N], dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; char G[N][N]; int vis[N][N]; void BFS(node s, int num) { node p, q; queue<node>Q; Q.push(s); memset(vis, 0, sizeof(vis)); vis[s.x][s.y] = 1; while(Q.size()) { p = Q.front(), Q.pop(); if(G[p.x][p.y]==‘@‘) { if(num==1) a[p.x][p.y] = p.step; if(num==2) a[p.x][p.y] += p.step; } 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(!vis[q.x][q.y] && q.x>=0 && q.x<n && q.y>=0 && q.y<m && G[q.x][q.y]!=‘#‘) { vis[q.x][q.y] = 1; Q.push(q); } } } } int main() { while(scanf("%d%d", &n, &m)!=EOF) { int i, j; node Y, M; memset(a, 0, sizeof(a)); for(i=0; i<n; i++) { scanf("%s", G[i]); for(j=0; j<m; j++) { if(G[i][j]==‘Y‘) Y.x=i, Y.y=j, Y.step=0; if(G[i][j]==‘M‘) M.x=i, M.y=j, M.step=0; } } BFS(Y, 1); BFS(M, 2); int ans=INF; for(i=0; i<n; i++) for(j=0; j<m; j++) if(G[i][j]==‘@‘ && vis[i][j]) ans = min(ans, a[i][j]); printf("%d\n", ans*11); } return 0; }
(广搜) Find a way -- hdu -- 2612
原文:http://www.cnblogs.com/YY56/p/4796657.html