rt，答案有几率比样例大一点，不知道为什么 /kk

思路是把斜向差分后的差分序列差分出来 /kel

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

inline 
int solve(vector<vector<int>> v, int k) {
	int n = v.size(), m = v[0].size(), ans = 0;
	vector<vector<int>> a(n, vector<int>(m));
	vector<vector<int>> b(n, vector<int>(m));
	for (int i = 1; i < n - k - 1; i++) {
		for (int j = 1; j < m - k - 1; j++) {
			if (!v[i][j]) continue;
			a[i][j]++, a[i][j + k + 1]--;
			b[i + k][j - 1]--, b[i][j - 1]++;
		}
	}
	for (int i = 0; i < n; i++) for (int j = 1; j < m; j++) a[i][j] += a[i][j - 1];
	for (int i = n - 1; i; i--) for (int j = 0; j < m; j++) b[i - 1][j] += b[i][j];
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) a[i][j] += b[i][j];
	for (int i = 1; i < n; i++) for (int j = 0; j < m - 1; j++) a[i][j] += a[i - 1][j + 1];
	for (int i = 1; i < n - k - 1; i++) for (int j = 1; j < m - k - 1; j++) ans = max(ans, a[i][j]);
	return ans;
}

int t, n, m, k, ans; char s[MAXN];

int main() {
	for (scanf("%d", &t); t--;) {
		scanf("%d%d%d", &n, &m, &k), ans = 0;
		vector<vector<int>> a(n + k + 2, vector<int>(m + k + 2));
		for (int i = 1; i <= n; i++) {
			scanf("%s", s + 1);
			for (int j = 1; j <= m; j++) if (s[j] == '#') a[i][j] = 1;
		}
		ans = max(ans, solve(a, k));
		reverse(a.begin() + 1, a.begin() + n + 1), ans = max(ans, solve(a, k));
		for (int i = 1; i <= n; i++) reverse(a[i].begin() + 1, a[i].begin() + m + 1);
		ans = max(ans, solve(a, k)); 
		reverse(a.begin() + 1, a.begin() + n + 1), ans = max(ans, solve(a, k));
		printf("%d\n", ans);
	}
}