CF35C. Fire Again 题解 bfs求最短路

题目链接：https://codeforces.com/problemset/problem/35/C

视频讲解：https://www.bilibili.com/video/BV1tZ1FYPELp/?p=4

以每个着火的点为起点求最短路，然后输出任意一个距离值最大的点即可。

需要注意的是：本题是文件输入输出。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2020;

int n, m, k, dis[maxn][maxn], ans; // ans 表示 dis[x][y] 最大值 

struct Node {
	int x, y;
};

int dir[4][2] = { -1, 0, 1, 0, 0, -1, 0, 1 };

bool in_map(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= m;
}

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	cin >> n >> m >> k;
	memset(dis, -1, sizeof dis);
	queue<Node> que;
	while (k--) {
		int x, y;
		cin >> x >> y;
		dis[x][y] = 0;
		que.push({x, y});
	}
	while (!que.empty()) {
		Node u = que.front();
		que.pop();
		for (int i = 0; i < 4; i++) {
			int x = u.x + dir[i][0],
				y = u.y + dir[i][1];
			if (in_map(x, y) && dis[x][y] == -1) {
				dis[x][y] = dis[u.x][u.y] + 1;
				que.push({x, y});
				ans = max(ans, dis[x][y]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (dis[i][j] == ans) {
				cout << i << " " << j << endl;
				return 0;
			}
		}
	}
	return 0;
}