Fan_HD's Blog

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
char Map[102][102];
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int Sp[102][102];
int Sx, Sy, N, M;
queue<pair<int, int> > Q;
inline bool check(int x, int y)
{
	return x >= 1 && x <= N && y >= 1 && y <= M && Map[x][y] != '#' && Map[x][y] != 'P' && !Sp[x][y];
}
int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i ++) scanf("%s", Map[i] + 1);
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= M; j ++)
			if (Map[i][j] == 'H')
			{
				Sx = i, Sy = j;
				break;
			}
	Sp[Sx][Sy] = 1;
	Q.push(make_pair(Sx, Sy));
	while (!Q.empty())
	{
		pair<int, int> u = Q.front();
		Q.pop();
		for (int i = 0, x, y; i < 4; i ++)
		{
			x = u.first + dx[i], y = u.second + dy[i];
			if (check(x, y))
			{
				Sp[x][y] = Sp[u.first][u.second] + 1;
				if (Map[x][y] != 'S') Q.push(make_pair(x, y));
			}
		}
	}
	int Res = 1 << 20;
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= M; j ++)
		if (Map[i][j] == 'S' && Sp[i][j])
			for (int k = 0; k < 4; k ++)
				if (Map[i + dx[k]][j + dy[k]] == 'S' && Sp[i + dx[k]][j + dy[k]]) Res = min(Res, Sp[i][j] + Sp[i + dx[k]][j + dy[k]]);
	if (Res == (1 << 20)) puts("Hi and Ho will not have lunch.");
	else printf("%d\n", Res - 2);
	return 0;
}