AcWing 3785. 战舰
原题链接
简单
作者:
小华老师
,
2021-07-30 19:43:22
,
所有人可见
,
阅读 570
真的麻烦 没有优化 直接模拟就能过
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, k;
char g[N][N]; //存整个区域
int f[N][N]; //存每个点的投放指数m
bool st1[N][N]; //标记能不能向右扩展
bool st2[N][N]; //标记能不能向下扩展
void add1(int h, int a, int b, int x) 更新第h行下标从 a 到 b 的投放次数
{
for(int i = a; i <= b - x + 1; i ++)
{
for(int j = i; j <= i + x - 1; j ++)
{
f[h][j] ++;
st1[h][j] = true; //标记一下下次遍历到不能再向右扩展,避免重复计算
}
}
}
void add2(int h, int a, int b, int x) //更新第h列下标从 a 到 b 的投放次数
{
for(int i = a; i <= b - x + 1; i ++)
{
for(int j = i; j <= i + x - 1; j ++)
{
f[j][h] ++;
st2[j][h] = true; //标记一下下次遍历到不能再向下扩展,避免重复计算
}
}
}
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
cin >> g[i][j];
memset(st1, 0, sizeof st1);
memset(st2, 0, sizeof st2);
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
if(g[i][j] == '.')
{
int m = j;
while(m <= n && g[i][m] == '.' && !st1[i][m]) m ++; //从左向右找到一个全部为“....”的区间右端点m - 1
if(m - j >= k) add1(i, j, m - 1, k);
int s = i;
while(s <= n && g[s][j] == '.' && !st2[s][j]) s ++;
//从上向下找到一个全部为“....”的区间下端点s - 1
if(s - i >= k) add2(j, i, s - 1, k);
}
}
}
int a = 1, b = 1;
int res = 0;
for(int i = 1; i <= n; i ++) //找最大值
{
for(int j = 1; j <= n; j ++)
{
if(f[i][j] > res)
{
res = f[i][j];
a = i;
b = j;
}
}
}
cout << a << ' ' << b << endl;
return 0;
}