310203: CF1799E. City Union
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
City Union
题意翻译
给出一张 $n \times m$ 的网格图，格子有黑白两种颜色。 初始时图中有两个黑色连通块。你需要把一些格子涂黑，满足以下两个条件： - 操作结束后图上只有一个连通块。 - 连通块中任意两个格子之间（只经过连通块里格子的）最短路径长度等于它们的曼哈顿距离。 请构造一种涂色方案，并最小化最终连通块的大小。若有多种最优方案，输出任意一种即可。 连通块为四连通。 多组数据，$1 \le t \le 5000$，$1 \le n,m \le 50$，$nm \ge 3$，$\sum nm \le 25000$。题目描述
You are given $ n \times m $ grid. Some cells are filled and some are empty. A city is a maximal (by inclusion) set of filled cells such that it is possible to get from any cell in the set to any other cell in the set by moving to adjacent (by side) cells, without moving into any cells not in the set. In other words, a city is a connected component of filled cells with edges between adjacent (by side) cells. Initially, there are two cities on the grid. You want to change some empty cells into filled cells so that both of the following are satisfied: - There is one city on the resulting grid. - The shortest path between any two filled cells, achievable only by moving onto filled cells, is equal to the Manhattan distance between them. The Manhattan distance between two cells $ (a, b) $ and $ (c, d) $ is equal to $ |a - c| + |b - d| $ . Find a way to add filled cells that satisfies these conditions and minimizes the total number of filled cells.输入输出格式
输入格式
Input consists of multiple test cases. The first line contains a single integer $ t $ , the number of test cases ( $ 1 \le t \le 5000 $ ). The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 50 $ , $ nm \geq 3 $ ). The next $ n $ lines describe the grid. The $ i $ -th line contains a string $ s_i $ of length $ m $ . $ s_{i,j} $ is '\#' if the cell in position $ (i, j) $ is filled, and '.' if it is empty. It is guaranteed that there are exactly two cities in the initial grid. It is guaranteed that the sum of $ n\cdot m $ over all test cases does not exceed $ 25\,000 $ .
输出格式
For each test case, output $ n $ lines, each containing a string of length $ m $ , describing the grid you create in the same format as the input. If there are multiple possible answers with the minimum number of filled cells print any.
输入输出样例
输入样例 #1
11
1 3
#.#
2 2
.#
#.
4 4
..##
...#
#...
##..
6 6
.##...
##....
......
....##
.....#
...###
6 5
.#..#
.#..#
.#..#
.#.##
.#...
##...
5 5
#####
#...#
#.#.#
#...#
#####
4 4
.##.
##.#
#.##
.##.
5 5
..###
....#
.....
#....
#....
5 6
.##...
##....
#....#
....##
...##.
6 5
..##.
...##
....#
#....
##...
.##..
5 4
..##
..#.
..#.
#...
#...输出样例 #1
###
.#
##
..##
..##
###.
##..
.##...
###...
..#...
..####
...###
...###
.####
.####
.####
.####
.#...
##...
#####
#####
#####
#####
#####
.##.
####
####
.##.
..###
..###
..#..
###..
#....
.##...
###...
######
...###
...##.
..##.
..###
..###
###..
###..
.##..
..##
..#.
..#.
###.
#...说明
In the first test case, we can add a single filled cell between the two cities to connect them. We can verify that the second condition is satisfied. In the second test case, we can also connect the cities with a single filled cell, while satisfying the second condition. In the third test case, note that if we filled the 3 cells in the top left, the cities would be connected, but the second condition would not be satisfied for cells $ (4, 2) $ and $ (2, 4) $ .Input
题意翻译
给出一张 $n \times m$ 的网格图，格子有黑白两种颜色。 初始时图中有两个黑色连通块。你需要把一些格子涂黑，满足以下两个条件： - 操作结束后图上只有一个连通块。 - 连通块中任意两个格子之间（只经过连通块里格子的）最短路径长度等于它们的曼哈顿距离。 请构造一种涂色方案，并最小化最终连通块的大小。若有多种最优方案，输出任意一种即可。 连通块为四连通。 多组数据，$1 \le t \le 5000$，$1 \le n,m \le 50$，$nm \ge 3$，$\sum nm \le 25000$。Output
**题目大意**：
给定一个 $n \times m$ 的网格图，每个格子非黑即白。初始时有两个黑色连通块。你的任务是涂黑一些格子，使得：
- 最终只有一个黑色连通块。
- 连通块中任意两个格子之间的最短路径长度等于它们的曼哈顿距离。
需要构造一种涂色方案，并最小化最终连通块的大小。如果有多种最优方案，输出其中任意一种即可。连通块是四连通的。有多组数据，满足 $1 \le t \le 5000$，$1 \le n,m \le 50$，$nm \ge 3$，$\sum nm \le 25000$。
**输入输出数据格式**：
**输入格式**：
- 第一行包含一个整数 $t$，表示测试用例的数量。
- 每个测试用例的第一行包含两个整数 $n$ 和 $m$。
- 接下来的 $n$ 行描述网格，第 $i$ 行包含一个长度为 $m$ 的字符串 $s_i$。如果 $s_{i,j}$ 是 '#'，表示格子 $(i, j)$ 是黑色；如果是 '.'，表示是白色。
- 保证初始网格中有且仅有两个黑色连通块。
- 所有测试用例的 $n \times m$ 之和不超过 $25,000$。
**输出格式**：
- 对于每个测试用例，输出 $n$ 行，每行包含一个长度为 $m$ 的字符串，描述构造的网格。
- 如果存在多种最小化填充格子的方案，输出其中任意一种。**题目大意**： 给定一个 $n \times m$ 的网格图，每个格子非黑即白。初始时有两个黑色连通块。你的任务是涂黑一些格子，使得： - 最终只有一个黑色连通块。 - 连通块中任意两个格子之间的最短路径长度等于它们的曼哈顿距离。 需要构造一种涂色方案，并最小化最终连通块的大小。如果有多种最优方案，输出其中任意一种即可。连通块是四连通的。有多组数据，满足 $1 \le t \le 5000$，$1 \le n,m \le 50$，$nm \ge 3$，$\sum nm \le 25000$。 **输入输出数据格式**： **输入格式**： - 第一行包含一个整数 $t$，表示测试用例的数量。 - 每个测试用例的第一行包含两个整数 $n$ 和 $m$。 - 接下来的 $n$ 行描述网格，第 $i$ 行包含一个长度为 $m$ 的字符串 $s_i$。如果 $s_{i,j}$ 是 '#'，表示格子 $(i, j)$ 是黑色；如果是 '.'，表示是白色。 - 保证初始网格中有且仅有两个黑色连通块。 - 所有测试用例的 $n \times m$ 之和不超过 $25,000$。 **输出格式**： - 对于每个测试用例，输出 $n$ 行，每行包含一个长度为 $m$ 的字符串，描述构造的网格。 - 如果存在多种最小化填充格子的方案，输出其中任意一种。
给定一个 $n \times m$ 的网格图，每个格子非黑即白。初始时有两个黑色连通块。你的任务是涂黑一些格子，使得：
- 最终只有一个黑色连通块。
- 连通块中任意两个格子之间的最短路径长度等于它们的曼哈顿距离。
需要构造一种涂色方案，并最小化最终连通块的大小。如果有多种最优方案，输出其中任意一种即可。连通块是四连通的。有多组数据，满足 $1 \le t \le 5000$，$1 \le n,m \le 50$，$nm \ge 3$，$\sum nm \le 25000$。
**输入输出数据格式**：
**输入格式**：
- 第一行包含一个整数 $t$，表示测试用例的数量。
- 每个测试用例的第一行包含两个整数 $n$ 和 $m$。
- 接下来的 $n$ 行描述网格，第 $i$ 行包含一个长度为 $m$ 的字符串 $s_i$。如果 $s_{i,j}$ 是 '#'，表示格子 $(i, j)$ 是黑色；如果是 '.'，表示是白色。
- 保证初始网格中有且仅有两个黑色连通块。
- 所有测试用例的 $n \times m$ 之和不超过 $25,000$。
**输出格式**：
- 对于每个测试用例，输出 $n$ 行，每行包含一个长度为 $m$ 的字符串，描述构造的网格。
- 如果存在多种最小化填充格子的方案，输出其中任意一种。**题目大意**： 给定一个 $n \times m$ 的网格图，每个格子非黑即白。初始时有两个黑色连通块。你的任务是涂黑一些格子，使得： - 最终只有一个黑色连通块。 - 连通块中任意两个格子之间的最短路径长度等于它们的曼哈顿距离。 需要构造一种涂色方案，并最小化最终连通块的大小。如果有多种最优方案，输出其中任意一种即可。连通块是四连通的。有多组数据，满足 $1 \le t \le 5000$，$1 \le n,m \le 50$，$nm \ge 3$，$\sum nm \le 25000$。 **输入输出数据格式**： **输入格式**： - 第一行包含一个整数 $t$，表示测试用例的数量。 - 每个测试用例的第一行包含两个整数 $n$ 和 $m$。 - 接下来的 $n$ 行描述网格，第 $i$ 行包含一个长度为 $m$ 的字符串 $s_i$。如果 $s_{i,j}$ 是 '#'，表示格子 $(i, j)$ 是黑色；如果是 '.'，表示是白色。 - 保证初始网格中有且仅有两个黑色连通块。 - 所有测试用例的 $n \times m$ 之和不超过 $25,000$。 **输出格式**： - 对于每个测试用例，输出 $n$ 行，每行包含一个长度为 $m$ 的字符串，描述构造的网格。 - 如果存在多种最小化填充格子的方案，输出其中任意一种。