Find a way HDU - 2612 (两路bfs+查表)

本文主要是介绍Find a way HDU - 2612 (两路bfs+查表)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

细节：
1.需要用dis数组保存到每个点的最短路，因为这里需要多次查询路径（如果kfc很多的话）
2. 整张图的dis初始化为一个很大的值，这里用0x3f3f3f3f，因为这足够大而且两个最大相加不会溢出～

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;const int maxn = 200 + 10;
const int INF = 0x3f3f3f3f;struct pos {int x, y;int cost;
};pos kfc[maxn*maxn];
pos p1;
pos p2;
int ans;
char m[maxn][maxn];
int N, M;
int vis[maxn][maxn];int dis[maxn][maxn][2];int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};bool judge(int x, int y) {return (x >= 0 && x < M && y >= 0 && y < N && m[y][x] != '#' && !vis[y][x]);
}void bfs(pos beg, int cur) {memset(vis, 0, sizeof(vis));queue<pos> qu;beg.cost = 0;qu.push(beg);pos temp;vis[beg.y][beg.x] = 1;while(!qu.empty()) {pos u = qu.front();  qu.pop();for(int i = 0; i < 4; i++) {int nx = u.x + dx[i];int ny = u.y + dy[i];if (judge(nx, ny)) {vis[ny][nx] = 1;temp.y = ny;temp.x = nx;temp.cost = u.cost + 1;dis[ny][nx][cur] = temp.cost;qu.push(temp);}}}
}int main() {//freopen("input.txt", "r", stdin);while(~scanf("%d%d", &N, &M)) {memset(dis, -1, sizeof(dis));getchar();pos t;int cnt = 0;for(int i = 0; i < N; i++) {for(int j = 0; j < M; j++) {dis[i][j][0] = dis[i][j][1] = INF;scanf("%c", &m[i][j]);if (m[i][j] == '@') {t.x = j;t.y = i;kfc[cnt++] = t;}else if (m[i][j] == 'Y') {p1.y = i;p1.x = j;dis[i][j][0] = 0;}else if (m[i][j] == 'M') {p2.y = i;p2.x = j;dis[i][j][1] = 0;}}getchar();}bfs(p1, 0);bfs(p2, 1);ans = INF;for(int i = 0; i < cnt; i++) {ans = min(ans, dis[kfc[i].y][kfc[i].x][0] + dis[kfc[i].y][kfc[i].x][1]);}printf("%d\n", ans * 11);}return 0;
}