AT_abc337_d 题解
yyrwlj
·
·
题解
题意简述
给定一个 n \times m 的矩阵，矩阵中的每个字母可以是 . 或 x 或 o。
可以花费一个代价让一个 . 变成 o。
问在矩阵中构造出一个 1 \times k 或 k \times 1 全都是 o 的矩阵的最小代价。若无法构造输出 -1。
## 思路
二维前缀和，维护子矩阵 `.` 和 `x` 的数量。
若矩阵内有 `x`，那么就无法在此矩阵构造。
否则将这个矩阵全变成 `o` 的代价就是矩阵中 `.` 的个数。
因为我们并不知道 $n$ 和 $m$ 单独的范围，所以可以使用 `vector` 来动态申请内存。
读入用 `vector` 套 `string` 即可。
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
int get(vector<vector<int> > &a,int x1,int _y1,int x2,int y2,int op = 2)
{
return a[x2][y2] - a[x2][_y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][_y1 - 1];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<string> a(n + 1);
for (int i=1;i<=n;i++)
{
cin >> a[i];
a[i] = " " + a[i];
}
vector<vector<int> > s1(n + 1), s2(n + 1);
s1[0].resize(m + 1);
s2[0].resize(m + 1);
for (int i=1;i<=n;i++)
{
s1[i].resize(m + 1);
s2[i].resize(m + 1);
for (int j=1;j<=m;j++)
{
s1[i][j] = s1[i - 1][j] + s1[i][j - 1] - s1[i - 1][j - 1];
s2[i][j] = s2[i - 1][j] + s2[i][j - 1] - s2[i - 1][j - 1];
if (a[i][j] == 'x')
s2[i][j] ++;
else if (a[i][j] == '.')
s1[i][j] ++;
}
}
int ans = 2e9;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if (a[i][j] == 'x')
continue;
if (j >= k && get(s2, i, j - k + 1, i, j, 1) == 0)
ans = min(ans, get(s1, i, j - k + 1, i, j));
if (i >= k && get(s2, i - k + 1, j, i, j, 1) == 0)
ans = min(ans, get(s1, i - k + 1, j, i, j));
}
if (ans > 1e9)
cout << -1 << endl;
else
cout << ans;
return 0;
}
```