[COCI2010-2011#7] POŠTAR - 邮递员的疲劳度

#\ [COCI2010-2011#7] PO\u0160TAR\n\n##\ 题目背景\n\nMirko 在一个山中小镇里得到了一个邮递员的差事。这个小镇可以用一个 $n \times n$ 的矩阵表示。每个区域有三种状态：用 `\texttt{K}` 表示房屋，用 `\texttt{P}` 表示邮局或用 `\texttt{.}` 表示牧场。此外，每个区域被分配一个高度。\n\n每天早晨，Mirko 都给镇上的每户人家送邮件。他从用 `\texttt{P}` 表示的区域开始。Mirko 只能水平、垂直或斜向移动到相邻的区域。他一旦送完最后一封邮件，就必须返回邮局。\n\nMirko 不知道他的工作会有多无聊。令 Mirko 在投递邮件时所到的最高处和最低处的高度之差等于他的疲劳度。帮他找出疲劳度最小的方式，让 Mirko 投递所有的邮件。\n\n##\ 题目描述\n\n给定一个 $n \times n$ 的矩阵。\n\n每个位置可能有 `\texttt{K}` `\texttt{P}` `\texttt{.}` 三种可能状态，此外还有一个高度 $h_{i,j}$。\n\n你需要从状态为 `\texttt{P}` 的位置开始，水平、垂直或斜向移动，经过所有状态为 `\texttt{K}` 的位置，最终回到起点。\n\n在这路程中，你需要让经过的位置的 $max_h-min_h$ 最小化。\n\n请你求出最小化的值。\n\n##\ 输入格式\n\n第一行包含一个整数 $n$。\n\n下面的 $n$ 行每行 $n$ 个字符表示矩阵。\n\n下面的 $n$ 行每行 $n$ 个正整数，表示区域高度。\n\n##\ 输出格式\n\n一个非负整数表示最小疲劳度。\n\n##\ 样例 #1\n\n###\ 样例输入 #1\n\n\n2\nP.\n.K\n2 1\n3 2\n\n\n###\ 样例输出 #1\n\n\n0\n\n\n##\ 样例 #2\n\n###\ 样例输入 #2\n\n\n3\nP..\n.KK\n...\n3 2 4\n7 4 2\n2 3 1\n\n\n###\ 样例输出 #2\n\n\n2\n\n\n##\ 样例 #3\n\n###\ 样例输入 #3\n\n\n3\nK.P\n...\nK.K\n3 3 4\n9 5 9\n8 3 7\n\n\n###\ 样例输出 #3\n\n\n5\n\n\n##\ 提示\n\n####\ 样例 1 解释\n\n从邮局开始，Mirko 可以直接移动到房屋，然后再回到邮局。因为这两个区域高度相同，所以 Mirko的疲劳等于 $0$。\n\n####\ 数据规模及约定\n\n\n对于矩阵，其中 `\texttt{P}` 将正好出现一次，而 `\texttt{K}` 将至少出现一次。\n\n对于 $100%$\ 的数据 $2 \le n \le 50$\n\n####\ 说明\n\n本题满分 $100$ 分。\n\n译自 \ COCI2010-2011 \ CONTEST #7 T4 PO\u0160TAR内容：##\ 思路解析\n\n这是一个图论问题，我们可以将输入的矩阵看作一个有向图。\n\n首先，我们需要找到起点和终点，即状态为 `\texttt{P}` 的位置。\n\n然后，我们可以使用广度优先搜索（BFS）来找到从起点到终点的最短路径。在搜索过程中，我们需要记录经过的位置的最高高度和最低高度。\n\n最后，我们将最高高度和最低高度的差值即为疲劳度。\n\n具体的做法如下：\n\n1. 遍历矩阵，找到起点和终点的坐标。\n\n2. 使用BFS来搜索从起点到终点的最短路径。在搜索过程中，我们需要记录经过的位置的最高高度和最低高度。\n\n3. 返回最高高度和最低高度的差值作为疲劳度。\n\n我们可以使用队列来实现BFS算法。\n\n##\ 代码实现\n\ncpp\n#include <iostream>\n#include <vector>\n#include <queue>\n#include <climits>\nusing namespace std;\ \ struct Point {\n int x;\ int y;\ };\ \ int main() {\n int n;\ cin >> n;\ \ vector<vector<char>> matrix(n, vector<char>(n));\ vector<vector<int>> heights(n, vector<int>(n));\ \ Point start, end;\ for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n cin >> matrix[i][j];\ if (matrix[i][j] == 'P') {\n start.x = i;\ start.y = j;\ }\ if (matrix[i][j] == 'K') {\n end.x = i;\ end.y = j;\ }\ }\ }\ \ for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n cin >> heights[i][j];\ }\ }\ \ vector<vector<bool>> visited(n, vector<bool>(n, false));\ vector<vector<pair<int, int>>> minMax(n, vector<pair<int, int>>(n, {INT_MAX, INT_MIN}));\ \ queue<Point> q;\ q.push(start);\ visited[start.x][start.y] = true;\ minMax[start.x][start.y] = {heights[start.x][start.y], heights[start.x][start.y]};\ \ int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};\ int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};\ \ while (!q.empty()) {\n Point curr = q.front();\ q.pop();\ \ for (int i = 0; i < 8; i++) {\n int nx = curr.x + dx[i];\ int ny = curr.y + dy[i];\ \ if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && matrix[nx][ny] != '.') {\n visited[nx][ny] = true;\ minMax[nx][ny].first = min(minMax[nx][ny].first, minMax[curr.x][curr.y].first);\ minMax[nx][ny].second = max(minMax[nx][ny].second, minMax[curr.x][curr.y].second);\ q.push({nx, ny});\ }\ }\ }\ \ int fatigue = minMax[end.x][end.y].second - minMax[end.x][end.y].first;\ cout << fatigue << endl;\ \ return 0;\ }\n\n\n##\ 复杂度分析\n\n该算法使用了BFS，时间复杂度为 $O(n^2)$，其中 $n$ 是矩阵的大小。\n\n空间复杂度为 $O(n^2)$，用于存储矩阵、高度、访问状态和最大最小高度。\n\n##\ 总结\n\n本题是一个简单的图论问题，使用BFS来搜索最短路径，求解最小疲劳度。通过记录经过的位置的最高高度和最低高度，可以得到最终的结果。\n