关注我,分享高质量每日一题题解~
b站同名账号分享力扣杯历届真题视频题解,也欢迎大家提出宝贵意见!
思路:前缀和
- 可能不是最优方法,但是是最先想到的方法
- 对于位置 $(x, y)$,我们通过预处理,记录 $(x, y)$ 左边和右边(包含该位置)分别有多少连续安全区域,假设分别为 $l, r$,那么总长度为 $l + r - 1$,那么可以放的战舰方式为 $(l + r - 1) - k + 1 = l + r - k$ 种。上边和下边同理,对应竖着放战舰的方式数量。
- 特别地,在预处理过程中,要将长度与 $k$ 取较小值。例如,在计算 $(x, y)$ 位置的方案时,就算右边连续 $10$ 个位置都是安全的,如果战舰长度为 $3$,那么最右边的几个位置就没法放。
- 代码中,利用 $left, right, up, down$ 四个数组分别记录一个位置 $(x, y)$ 左右上下的连续安全区域。最终的种类数要与 $0$ 取较大值,防止长度不够放战舰的情况。
代码(C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<vector<int>> a(n + 1, vector<int>(n + 1));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
char c;
cin >> c;
if(c == '.') {
a[i][j] = 1;
}
}
}
vector<vector<int>> left(n + 2, vector<int>(n + 2));
vector<vector<int>> right(n + 2, vector<int>(n + 2));
vector<vector<int>> up(n + 2, vector<int>(n + 2));
vector<vector<int>> down(n + 2, vector<int>(n + 2));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(a[i][j]) {
left[i][j] = left[i][j - 1] + 1;
up[i][j] = up[i - 1][j] + 1;
}
left[i][j] = min(left[i][j], k);
up[i][j] = min(up[i][j], k);
}
}
for(int i = n; i >= 1; i--) {
for(int j = n; j >= 1; j--) {
if(a[i][j]) {
right[i][j] = right[i][j + 1] + 1;
down[i][j] = down[i + 1][j] + 1;
}
right[i][j] = min(right[i][j], k);
down[i][j] = min(down[i][j], k);
}
}
int ret = 0, x = 1, y = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(a[i][j]) {
int cnt = max(left[i][j] + right[i][j] - k, 0) + max(up[i][j] + down[i][j] - k, 0);
if(ret < cnt) {
ret = cnt;
x = i;
y = j;
}
}
}
}
cout << x << " " << y << endl;
return 0;
}