ABC 337

D. Cheating Gomoku Narabe

        （1） 暴力解法

                对于每个非 ' x ' 的点，都作为起点分别向右或向下枚举，如果 k 个之内出现 ' x ' 就退出，否则对出现的 ' . ' 的个数取 min。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;int T, n, m, k, cnt, ans;
string s[N];signed main()
{cin >> n >> m >> k;ans = INF;for (int i = 1; i <= n; i ++){cin >> s[i];s[i] = ' ' + s[i];}for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++){if (j + k - 1 > m)break;if (s[i][j] != 'x'){int cnt1 = 0, p1 = 0;for (int z = 0; z < k; z ++){if (s[i][j + z] == '.')cnt1 ++;if (s[i][j + z] == 'x'){p1 = 1;break;}}if (p1 == 0)ans = min(ans, cnt1);}}for (int i = 1; i <= n; i ++){if (i + k - 1 > n)break;for (int j = 1; j <= m; j ++)if (s[i][j] != 'x'){int cnt2 = 0, p2 = 0;for (int z = 0; z < k; z ++){if (s[i + z][j] == '.')cnt2 ++;if (s[i + z][j] == 'x'){p2 = 1;break;}}if (p2 == 0)ans = min(ans, cnt2);		}}if (ans == INF)ans = -1;cout << ans;return 0;
}

        （2）优化

                注意到这里固定了区间长度 k，典型的滑动窗口解法。统计窗口内 ' . ' 和 ' x ' 的个数即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;int T, n, m, k, cnt, ans;
string s[N];signed main()
{cin >> n >> m >> k;ans = INF;for (int i = 1; i <= n; i ++){cin >> s[i];s[i] = ' ' + s[i];}for (int i = 1; i <= n; i ++){int cnt1 = 0, cnt2 = 0; for (int j = 1; j <= m; j ++){cnt1 += (s[i][j] == '.');cnt2 += (s[i][j] == 'x');if (j < k)	continue;if (cnt2 == 0)ans = min(ans, cnt1);cnt1 -= (s[i][j - k + 1] == '.');cnt2 -= (s[i][j - k + 1] == 'x');}}for (int j = 1; j <= m; j ++){int cnt1 = 0, cnt2 = 0; for (int i = 1; i <= n; i ++){cnt1 += (s[i][j] == '.');cnt2 += (s[i][j] == 'x');if (i < k)	continue;if (cnt2 == 0)ans = min(ans, cnt1);cnt1 -= (s[i - k + 1][j] == '.');cnt2 -= (s[i - k + 1][j] == 'x');}}if (ans == INF)ans = -1;cout << ans;return 0;
}