一个安全区域会存战舰一部分
所以只需要找竖直方向和水平方向包含此安全区域的方法个数
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k;
int area[105][105];
int ans= 0;
int bfs(int x,int y,int k){
int sum = 0;
int x1 = x + 1;
while(x1 <= n && area[x1][y] == 1)x1++;
int x2 = x - 1;
while(x2 >= 1 && area[x2][y] == 1)x2--;
if(x1 - x2 >= k + 1)sum += min(k,min(x1 - x2 - k,min(x - x2,x1 - x)));
int y1 = y - 1;
while(y1 >= 1 && area[x][y1] == 1)y1--;
int y2 = y1 + 1;
while(area[x][y2])y2++;
if(y2 - y1 >= k + 1)sum += min(k,min(y2 - y1 - k,min(y - y1,y2 - y)));
return sum;
}
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
char c;
cin >> c;
if(c == '#')area[i][j] = 0;
else if(c == '.')area[i][j] = 1;
}
}
int x = 1,y = 1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(area[i][j] == 1){
int tem = bfs(i,j,k);
if(tem > ans){
x = i;
y = j;
ans = tem;
}
}
}
}
cout << x << " " << y << endl;
return 0;
}