题目

Problem Statement

有一个大小为 H 行 W 列的网格。令 (i, j) 表示第 i 行第 j 列的单元格。

每个单元格包含一个字符 o、x 或 .。其由 H 个长度为 W 的字符串 S_1, S_2, \ldots, S_H 表示，单元格 (i, j) 中的字符是字符串 S_i 中的 j 个字符。

对于此网格，您可以重复进行任意多次以下操作（可能为****次）：

  • 选择一个带有字符 . 的单元格，并将该单元格中的字符更改为 o。

确定是否存在连续 K 个水平或竖直的 o 组成的序列（换言之，至少满足以下两个条件中的其中一个）。

  • 对于满足 1 \leq i \leq H 和 1 \leq j \leq W-K+1 的整数对 (i, j) ，使得单元格 (i, j), (i, j+1), \ldots, (i, j+K-1) 中的字符都是 o。
  • 对于满足 1 \leq i \leq H-K+1 和 1 \leq j \leq W 的整数对 (i, j) ，使得单元格 (i, j), (i+1, j), \ldots, (i+K-1, j) 中的字符都是 o。

如果存在，输出满足条件所需的最少操作次数。

Constraints

  • H、 W 和 K 皆为整数。
  • 1 \leq H
  • 1 \leq W
  • H \times W \leq 2 \times 10^5
  • 1 \leq K \leq \max\lbrace H, W \rbrace
  • S_i 是长度为 W 的字符串，且仅由 o、 x 和 . 组成。

Input

输入格式如下：

  • H W K
  • S_1
  • S_2
  • \vdots
  • S_H

Output

如果无论如何操作都无法满足条件，输出 -1 。 否则，输出满足条件所需的最少操作次数。

解法

思路

遍历所有行和列，枚举所有定长的序列即可。如果 W < K 则无需按行枚举；同理若 H < K 则无需按列枚举。

找到符合条件的序列后，根据序列中 . 的数量确定操作次数，并维护操作次数的最小值，时间复杂度为 O(H \times W) 。

可以对思路进行一些小优化：使用一个临时变量存储当前序列的长度，遇到 x 时重置长度，否则对临时变量执行自增；当序列长度达到 K 时更新当前操作次数的最小值，可以略微减小复杂度常数。

实现

首先应该开一个二维 char 数组来存储字符。

由于 H \times W 的最大值为 2 \times 10^5 ，意味着不能直接开 char 数组，否则会爆 MLE 。

可以考虑使用 VLA ，即传入变量之后再开数组：

cin >> h >> w >> k;
char arr[h + 10][w + 10];

也可以使用 vector 进行数组存储。

传入数组之后开始遍历：

//此为按列遍历代码，按行遍历同理  
  for (int i = 1; i <= w; ++i) {
    int tmp = 0, tans = 0;
    // tmp 存储当前序列长度；tans 存储'.'的数量，即操作次数
    for (int j = 1; j <= h; ++j) {
      if (arr[j][i] == 'o') {
        tmp++;
      } else if (arr[j][i] == '.') {
        // 若当前单元格字符为'.'，则令 tans 自增
        tmp++;
        tans++;
      } else {
        // 若当前单元格字符为'x'，则重置 tmp 和 tans
        tmp = 0;
        tans = 0;
      }
      if (tmp >= k) {
        b = true; // 此处 b 为全局变量，表示答案是否存在
        ans = min(ans, tans); // 更新答案的最小值
        tmp--;
        if (arr[j - k + 1][i] == '.') tans--;
      }
    }
  }

最后输出 ans 即可。若答案不存在，则输出 -1 。