算法
(前計算) $O(HW(H + W))$
对于把灯放到每个非障碍物的位置而言,它所能照射的方块数为它在当前行所能照射的方块数 +
它在当前列所能照射的方块数 - 1
。
我们只需要预计算把灯放置在每个非障碍物的位置所能照射的方块数。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::vector;
using std::string;
int main() {
int h, w;
cin >> h >> w;
vector<string> s(h);
rep(i, h) cin >> s[i];
vector<vector<int>> cnt(h, vector<int>(w));
rep(i, h) {
vector<int> done(w);
rep(j, w) {
if (s[i][j] == '#') continue;
if (done[j]) continue;
int l = 0;
while (j + l < w) {
if (s[i][j + l] == '#') break;
++l;
}
rep(k, l) {
cnt[i][j + k] += l;
done[j + k] = 1;
}
}
}
rep(j, w) {
vector<int> done(h);
rep(i, h) {
if (s[i][j] == '#') continue;
if (done[i]) continue;
int l = 0;
while (i + l < h) {
if (s[i + l][j] == '#') break;
++l;
}
rep(k, l) {
cnt[i + k][j] += l;
done[i + k] = 1;
}
}
}
int ans = 0;
rep(i, h)rep(j, w) ans = max(ans, cnt[i][j] - 1);
cout << ans << '\n';
return 0;
}