hiho1092_have lunch together

题目

    两个人从同一个点出发，在一个餐厅中寻找两个相邻的座位，需要是的从出发点到达座位的距离总和最短。题目链接: Have Lunch Together
    最短路程，一开始以为要用dijkstra等图算法，发现完全不用，直接用BFS进行搜索，并标记到达每个点的最短距离。一次BFS求出从起始点 到达所有点的最短距离之后，再遍历每个点，判断该点是否是合法的座位（能够从起始点到达，且为座位），然后对每个座位，看它四周的点是否是合法的座位，然 后求出两个合法的座位的最短距离和的最小值。

实现

#include<stdio.h>
#include<cmath>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<deque>
#include<string>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define min(a, b) (a) < (b)? (a) : (b)
char gMap[105][105];
int gMinDist[105][105];
int gMoveStep[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
struct Node {
	int row;
	int col;
	int step;
	Node(int r, int c, int s) :
		row(r), col(c), step(s) {};
};
//BFS 求出从出发点到达每个能够到达的点的最短距离
void Bfs(int start_row, int start_col) {
	queue<Node> Q;
	Node node(start_row, start_col, 0);
	Q.push(node);
	gMinDist[start_row][start_col] = 0;
	while (!Q.empty()) {
		node = Q.front();
		Q.pop();
		for (int i = 0; i < 4; i++) {
			int next_row = node.row + gMoveStep[i][0];
			int next_col = node.col + gMoveStep[i][1];
			if ((gMap[next_row][next_col] == 'S' || gMap[next_row][next_col] == '.') && gMinDist[next_row][next_col] == -1) {
				gMinDist[next_row][next_col] = node.step + 1;
				if(gMap[next_row][next_col] == '.')
					Q.push({ next_row, next_col, node.step + 1 });
			}
		}
	}
}
int MinDist(int n, int m) {
	int min_dist = 1 << 29;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (gMap[i][j] == 'S' && gMinDist[i][j] != -1) { // 为一个座位，且在BFS过程中能够到达
				for (int k = 0; k < 4; k++) {
					int ii = i + gMoveStep[k][0];
					int jj = j + gMoveStep[k][1];
					// 为一个座位，且在BFS过程中能够到达
					if (ii >= 1 && ii <= n && jj >= 1 && jj <= m && gMap[ii][jj] == 'S' && gMinDist[ii][jj] != -1) {
						min_dist = min(min_dist, gMinDist[i][j] + gMinDist[ii][jj]);
					}
				}
			}
		}
	}
	return min_dist;
}
int main() {
	int n, m, start_row, start_col;
	scanf("%d %d", &n, &m);
	memset(gMap, '#', sizeof(gMap));
	memset(gMinDist, -1, sizeof(gMinDist));
	for (int i = 1; i <= n; i++) {
		getchar();
		for (int j = 1; j <= m; j++) {
			scanf("%c", &gMap[i][j]);
			if (gMap[i][j] == 'H') {
				start_row = i;
				start_col = j;
			}
		}
	}
	Bfs(start_row, start_col);
	int min_dist = MinDist(n, m);
	if (min_dist == (1 << 29)) {
		printf("Hi and Ho will not have lunch.
");
	}else
		printf("%d
", min_dist);
	return 0;
}