Hdu2612Find a way

题意：

给一个图，Y和M两个人分别出发，想去@，问最短时间能到达哪个@。

思路：2遍bfs

坑点：要判断每个@点两个人是否都可达。

#include 
#include  
#include 
#include 
#define fi first
#define se second
#define pii pair
using namespace std;
typedef long long LL;
const int maxn = 200+5;
const int INF = 0x3f3f3f3f;int moved[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
char G[maxn][maxn];
int n, m, vis[maxn][maxn]; 
int d[2][maxn][maxn];struct Node{int x,y,step;Node(int a = 0, int b = 0, int c = 0):x(a),y(b),step(c){}
};
Node Y,M;void bfs(int cur){memset(vis, 0, sizeof(vis));queue Q;if(cur == 0) Q.push(Y);else Q.push(M);Node t;while(!Q.empty()){t = Q.front(); Q.pop(); for(int i = 0; i < 4; ++i){int x2 = t.x + moved[i][0];int y2 = t.y + moved[i][1];int s2 = t.step + 1;if(x2 >= 0&&x2 < n&&y2 >= 0&&y2 < m&&G[x2][y2] != '#'&&!vis[x2][y2]){if(G[x2][y2] == '@') d[cur][x2][y2] = s2;vis[x2][y2] = 1;Q.push(Node(x2,y2,s2));} }} 
}int main()
{freopen("in.txt","r",stdin);while(scanf("%d %d",&n,&m) == 2){for(int i = 0; i < n; ++i) scanf("%s",G[i]);for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){if(G[i][j] == 'Y'){Y.x = i; Y.y = j; Y.step = 0;}else if(G[i][j] == 'M'){M.x = i; M.y = j; M.step = 0;}}}memset(d[0],0,sizeof(d[0])); bfs(0);memset(d[1],0,sizeof(d[1])); bfs(1);int ans = INF;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){if(G[i][j] == '@'&&d[0][i][j] > 0&&d[1][i][j] > 0)ans = min(ans, d[0][i][j]+d[1][i][j]);}}printf("%d\n",ans*11);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！