【固定滑窗】20232Q2-探索地块建立
题目描述与示例
题目描述
给一块n * m的地块，相当于 n * m的二维数组，每个元素的值表示这个小地块的发电量；求在这块地上建立正方形的边长为 c的发电站，发电量满足目标电量 k 的地块数量。
输入描述
第一行为四个按空格分隔的正整数，分别表示 n，m，c，k。后面 n 行整数，表示每个地块的发电量
输出描述
输出满足条件的地块数量
示例一
输入
2 5 2 6
1 3 4 5 8
2 3 6 7 1
输出
4
说明
满足条件的地块有以下几种 第一种：
1 3
2 3
第二种：
3 4
3 6
第三种：
4 5
6 7
第四种：
5 8
7 1
示例二
输入
4 5 2 6
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
输出
12
解题思路
本题的暴力解法是找到所有的c*c的地块并进行求和运算，这样的时间复杂度为O(nmc*2)，在此不进行赘述。
由于地块的大小固定为c*c，我们要搜索的其实是grid中所有大小为c*c的窗口中的值的和，这显然可以用固定滑窗的思路来完成，基本框架也为滑窗三问三答。
但本题的难点在于，grid是一个二维数组，c*c的地块也是一个二维的滑窗，我们需要在两个方向上进行滑窗过程。
首先考虑行方向（横向，向右）的滑窗。以示例二为例，只考虑第一行的话，有如下滑窗过程：
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
上述过程可以由函数slide_windows_in_row(grid, win_sum, i, m, c, k)来实现，即
def slide_windows_in_row(grid, win_sum, i, m, c, k):
global ans
if win_sum >= k:
ans += 1
for right in range(c, m):
for row in range(i, i+c):
win_sum -= grid[row][right-c]
win_sum += grid[row][right]
if win_sum >= k:
ans += 1
除了行方向的滑窗，还需要考虑列方向（纵向，向下）的滑窗。同样以示例二为例，存在以下过程：
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
1 3 4 5 8
2 3 6 7 1
而每一个列方向的第一个窗口，都可以通过调用slide_windows_in_row(grid, win_sum, i, m, c, k)在行方向的滑动。故代码为
for i in range(0, n-c):
for j in range(c):
windows_sum -= grid[i][j]
windows_sum += grid[i+c][j]
slide_windows_in_row(grid, windows_sum, i+1, m, c, k)
要注意，函数slide_windows_in_row(grid, win_sum, i, m, c, k)中的参数i，为当前搜索地块最上方那一行的行索引。
代码
解法
# 题目：2023Q2-探索地块建立
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：固定滑窗
# 代码看不懂的地方，请直接在群上提问
# 输入grid长宽n和m，地块正方形边长c，地块最小发电量k
n, m, c, k = map(int, input().split())
# 输入二维网格grid
grid = list()
for i in range(n):
grid.append(list(map(int, input().split())))
# 在行方向，即横向进行滑动窗口的函数
# (i,j)表示该地块左上角坐标的行索引和列索引，仅需要行索引i
def slide_windows_in_row(grid, win_sum, i, m, c, k):
# 设置答案变量ans为全局变量，可以在这个函数中进行修改
global ans
# 考虑第一个窗口的情况
if win_sum >= k:
ans += 1
# 窗口进行横向移动
for right in range(c, m):
# 每次横移，最左边的列即要在地块中移除，最右边的列要加入到地块中
# 考虑当前地块每一行的情况，当前地块行索引的范围是range(i, i+c)
# A1 A2
for row in range(i, i+c):
# 最左列要从win_sum中减去
win_sum -= grid[row][right-c]
# 最右列要往win_sum中添加
win_sum += grid[row][right]
# A3
if win_sum >= k:
ans += 1
# 排除特殊情况，地块的边长c大于n或m
# 无法找到任何一个地块，输出0
if c > n or c > m:
print(0)
# 否则可以进行二维的固定滑窗
else:
ans = 0
# 求出第一个地块的和，其左上角(i,j) = (0,0)
# 变量windows_sum_first_per_col表示每一列的第一个c*c的窗口和
windows_sum = sum(grid[i][j] for i in range(c) for j in range(c))
# 考虑第一行的情况
slide_windows_in_row(grid, windows_sum, 0, m, c, k)
# 窗口进行纵向移动
for i in range(0, n-c):
# 每次纵移，最上边的行即要在地块中移除，最下边的行要加入到地块中
# 考虑当前地块每一列的情况，当前地块列索引的范围是range(0, c)
for j in range(c):
windows_sum -= grid[i][j]
windows_sum += grid[i+c][j]
# 构建得到新的一个地块，可以再一次调用函数slide_windows_in_row()
# 进行横向移动，注意此处地块最上方的行的索引为i+1
slide_windows_in_row(grid, windows_sum, i+1, m, c, k)
# 考虑了所有地块，输出ans
print(ans)
时空复杂度
时间复杂度：O(nmc)。需要考虑(n-c)*(m-c)个地块，遍历的时间复杂度为O((n-c)*(m-c)) = O(nm)，每次计算得到一个新地块，还需要遍历c个位置，故总的时间复杂度为O(nmc)。
空间复杂度：O(1)。无需额外空间。
