A28418. 荒地开垦
填空题
较难
知识点
题目描述
荒地开垦
题目描述
小杨有一大片荒地，可以表示为一个 n行 m列的网格图。
小杨想要开垦这块荒地，但荒地中一些位置存在杂物，对于一块不存在杂物的荒地，该荒地可以开垦当且仅当其上下左右四个方向相邻的格子均不存在杂物。
小杨可以选择至多一个位置，清除该位置的杂物，移除杂物后该位置变为荒地。小杨想知道在清除至多一个位置的杂物的情况下，最多能够开垦多少块荒地。
输入格式
第一行包含两个正整数n，m ，含义如题目所示。
之后n行，每行包含一个长度为m且仅包含字符 . 和 # 的字符串。如果为 . ，代表该位置为荒地，如果为 # ，代表该位置为杂物。
输出格式
输出一个整数，代表在清除至多一个位置的杂物的情况下，最多能够开垦的荒地块数。
样例
输入样例1
3 5
.....
.#..#
.....输出样例1
11样例解释
移除第二行从左数第二块空地的杂物后：
.....
....#
.....第一行从左数前4块荒地，第二行从左数前3块荒地，第三行从左数前4块荒地，均可开垦，4+3+4=11。
数据范围
对于全部数据，保证有1≤n，m≤1000 。
参考答案
N = 1005
mat = [[''] * N for _ in range(N)]
a = [[0] * N for _ in range(N)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
n, m = map(int, input().split())
for i in range(1, n + 1):
line = input().strip()
for j in range(1, m + 1):
mat[i][j] = line[j - 1]
ans = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
num = 0
p = -1
for k in range(4):
ni, nj = i + d[k][0], j + d[k][1]
if mat[ni][nj] == '#':
num += 1
p = k
if mat[i][j] == '.' and num == 1:
ni, nj = i + d[p][0], j + d[p][1]
a[ni][nj] += 1
elif mat[i][j] == '.' and num == 0:
ans += 1
elif mat[i][j] == '#' and num == 0:
a[i][j] += 1
mx = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
mx = max(mx, a[i][j])
print(ans + mx)
上一题
下一题