题解 CF965B 【Battleship】
_Cloud_
2020-10-26 23:05:56
# 枚举
不用记忆化这么麻烦，直接暴力枚举哪些位置可以放船：有条理枚举，先**横向枚举**所有**横着放**的船，再**纵向枚举**所有**竖着放**的船。最后再依次寻找哪个点被覆盖最多次。
### 特别注意：当一组数据为n=1,k=1时，输出0 0是会WA的,因为它不在任何单元中。 机翻↓
```cpp
如果有多个答案，请输出其中任何一个。 特别是，如果没有船只可以放置在现场，则可以输出任何单元。
```
所以我的代码特判了这个数据，输出n n。或者将答案初始化成任意一个坐标都可以防这组hack数据。
###### 题外话：目前这个是最快的，比记忆化还快。。。
### $Code$
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
char s[N][N];
int a[N][N], ans, ansi, ansj;
int main() {
int n, k;
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%s", s[i] + 1);
for (int i = 1; i <= n; i++) {//枚举横向放船
for (int j = 1; j + k - 1 <= n; j++) {//因为从j开始数k个为： j+0, j+1, j+2 ...j+k-1，故循环到j+k-1
bool ok = true;
for (int p = 0; p < k; p++) {//同理
if (s[i][p + j] == '#') { ok = false; break; }//不满足放船，退出
}
if (ok == true) { for (int p = 0; p < k; p++) a[i][p + j]++; }//满足，每个点答案+1
}
}
for (int i = 1; i + k - 1 <= n; i++) {//枚举纵向放船,因为是纵向，所以i+k-1<=n
for (int j = 1; j <= n; j++) {
bool ok = true;
for (int p = 0; p < k; p++) {
if (s[i + p][j] == '#') { ok = false; break; }//不满足，退出
}
if (ok == true) { for (int p = 0; p < k; p++) a[i + p][j]++; }//满足，记录答案
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (ans < a[i][j]) { ans = a[i][j]; ansi = i, ansj = j; }//枚举每个点的覆盖次数，找最大的
if (ans == 0)//特判
printf("%d %d\n", n, n);
else
printf("%d %d\n", ansi, ansj);//正常输出
return 0;
}
```
###### ~~求管理大大通过o(*￣▽￣*)ブ~~