(暴力枚举) $O(n^2)$
直接模拟就好了,用一个数组记录每个点的投放指数,用两次for,一次枚举横着放的,一次枚举竖着放的,枚举有几点是连续的’.’,如果连续的数量为k,路径的每个点都加一,然后最后枚举每个点的投放指数就可以了
C++ 代码
#include <iostream>
using namespace std;
char mp[105][105];//记录地图
int n,k;
int res[105][105]; //用来投放安全指数
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> mp[i][j];
for(int i = 1; i <= n; i ++ ) //横着放
{
for(int j = 1; j <= n; j ++ )
{
int x = i,y = j,t = 0;
while(mp[x][y] == '.' && t < k)
{
y++;
t++;
}
if(t == k) //如果可以放下一个战舰
{
y--;
while(mp[x][y] == '.' && t) //逆序回到'#'的位置,沿途每个投放指数加一
{
t--;
res[x][y]++;
y--;
}
}
}
}
for(int i = 1; i <= n; i ++ ) //竖着放
{
for(int j = 1; j <= n; j ++ )
{
int x = i,y = j,t = 0;
while(mp[x][y] == '.' && t < k)
{
x++;
t++;
}
if(t >= k)
{
x--;
while(mp[x][y] == '.' && t)
{
t--;
res[x][y]++;
x--;
}
}
}
}
int ans = 0;
int x = 1 ,y = 1;
for(int i = 1 ;i <= n;i ++ ) //遍历枚举最大值
{
for(int j = 1;j <= n; j ++ )
{
if(res[i][j] > ans)
{
ans = res[i][j];
x = i;
y = j;
}
}
}
cout << x << ' ' << y ;
}