1985H1. Maximize the Largest Component (Easy Version)
brute force, data structures, dfs and similar, dsu, graphs, implementation, 1700,
https://codeforces.com/problemset/problem/1985/H1
Easy and hard versions are actually different problems, so read statements of both problems completely and carefully. The only difference between the two versions is the operation.
Alex has a grid with 𝑛 rows and 𝑚 columns consisting of '.' and '#' characters. A set of '#' cells forms a connected component if from any cell in this set, it is possible to reach any other cell in this set by only moving to another cell in the set that shares a common side. The size of a connected component is the number of cells in the set.
In one operation, Alex selects any row 𝑟 (1≤𝑟≤𝑛) or any column 𝑐 (1≤𝑐≤𝑚), then sets every cell in row 𝑟 or column 𝑐 to be '#'. Help Alex find the maximum possible size of the largest connected component of '#' cells that he can achieve after performing the operation at most once.
Input
The first line of the input contains a single integer 𝑡 (1≤𝑡≤104) — the number of test cases.
The first line of each test case contains two integers 𝑛 and 𝑚 (1≤𝑛⋅𝑚≤106) — the number of rows and columns of the grid.
The next 𝑛 lines each contain 𝑚 characters. Each character is either '.' or '#'.
It is guaranteed that the sum of 𝑛⋅𝑚 over all test cases does not exceed 106.
Output
For each test case, output a single integer — the maximum possible size of a connected component of '#' cells that Alex can achieve.
Example
input
6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.output
1
6
9
11
15
30Note
In the second test case, it is optimal for Alex to set all cells in column 2 to be '#'. Doing so will lead to the largest connected component of '#' having a size of 6.
In the third test case, it is optimal for Alex to set all cells in row 2 to be '#'. Doing so will lead to the largest connected component of '#' having a size of 9.
In the fourth test case, it is optimal for Alex to set all cells in row 4 to be '#'. Doing so will lead to the largest connected component of '#' having a size of 11.
【尹显齐 2500011456 物理学院】
首先，我们还是要搜索出里面所有的连通体，并存储每一个"#"对应的连通体编号。然后，当选择某一行/某一列来填满时，遍历填满之后所能连通的全部连通体（通过遍历这一行/列每一个点上下/左右的点），将这些连通体的大小加起来，加上这一行/列原先没有被填上的点数量，就得到最终的连通体大小，答案就是遍历完之后取最大值。
看上去这个题并不难，但是实际提交时你会发现，使用python提交仍然会超时。那有人肯定就问了：用pypy不就完了吗？但是用过pypy的人都知道，在pypy中使用的sys.setrecursionlimit()会直接影响到内存大小，让你直接爆内存。这也意味着，我们不能够使用函数递归的方式写dfs，而应该使用（不为人所知的）栈来写。
用栈实现dfs和用队列实现bfs的方式很像，唯一不同之处在于栈是从栈尾pop出元素，而队列是从队首pop。
for _ in range(int(input())):
n,m = map(int,input().split())
grid = [input() for _ in range(n)]
found = [[0]*m for _ in range(n)]
islands = [[0]*m for _ in range(n)]
sizedic = {}
def dfs(i,j,num):
found[i][j] = 1
size = 1
islands[i][j] = num
stack = [(i,j)]
while stack:
x,y = stack.pop()
for a,b in [(-1,0),(1,0),(0,1),(0,-1)]:
if 0<=x+a<n and 0<=y+b<m and found[x+a][y+b] == 0 and grid[x+a][y+b] == "#":
stack.append((x+a,y+b))
islands[x+a][y+b] = num
found[x+a][y+b] = 1
size += 1
return size
num = 0
for i in range(n):
for j in range(m):
if grid[i][j] == "#" and found[i][j] == 0:
num += 1
sizedic[num] = dfs(i,j,num)
ans,cur = 0,0
for i in range(n):
seen = set()
cur = 0
for j in range(m):
if islands[i][j]:
seen.add(islands[i][j])
else:
cur += 1
if i > 0 and islands[i-1][j]:
seen.add(islands[i-1][j])
if i < n-1 and islands[i+1][j]:
seen.add(islands[i+1][j])
for c in seen:
cur += sizedic[c]
ans = max(ans,cur)
for j in range(m):
seen = set()
cur = 0
for i in range(n):
if islands[i][j]:
seen.add(islands[i][j])
else:
cur += 1
if j > 0 and islands[i][j-1]:
seen.add(islands[i][j-1])
if j < m-1 and islands[i][j+1]:
seen.add(islands[i][j+1])
for c in seen:
cur += sizedic[c]
ans = max(ans,cur)
print(ans)（PS：可以挑战一下用pythonAC）