有道网站收录提交入口/软文推广收费

给定一个 $n\times n$ 的字符矩阵，表示一片海域。

矩阵中 # 表示暗礁区域，. 表示安全区域。

现在要将一个 $1\times k$ 的战舰投放到海域中。

投放时，战舰不可接触到暗礁区域。

战舰可以横着投放，也可以竖着投放。

在投放完成后，每个安全区域要么包含战舰的一部分，要么不包含。

对于某个安全区域，如果所有可能的投放方式中，共有 $m$ 种不同的投放方式，满足该区域包含战舰的一部分，那么就称该区域的投放指数为 $m$。

请确定投放指数最大的安全区域的位置坐标。

输入格式
第一行包含两个整数 $n$ 和 $k$。

接下来 $n$ 行，每行包含一个长度为 $n$ 的字符串，表示海域。

输出格式
输出投放指数最大的安全区域的行、列坐标。

行从上到下，从 $1$ 开始计数，列从左到右，从 $1$ 开始计数。

如果答案不唯一，输出任意合理方案均可。

如果海域中根本无法投放战舰，则输出任意区域均可。

数据范围
$1\le k\le n\le 100$

输入样例1：

4 3
#..#
#.#.
....
.###

输出样例1：

3 2

输入样例2：

10 4
#....##...
.#...#....
..#..#..#.
...#.#....
.#..##.#..
.....#...#
...#.##...
.#...#.#..
.....#..#.
...#.#...#

输出样例2：

6 1

输入样例3：

19 6
##..............###
#......#####.....##
.....#########.....
....###########....
...#############...
..###############..
.#################.
.#################.
.#################.
.#################.
#####....##....####
####............###
####............###
#####...####...####
.#####..####..#####
...###........###..
....###########....
.........##........
#.................#

输出样例3：

1 8

#include<iostream>using namespace std;const int N = 110;int n, k;
char g[N][N];int main(){scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++)scanf("%s", g[i] + 1);int x = 1, y = 1, res = 0;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(g[i][j] == '.'){int l = j, r = j;while(l >= 1 && g[i][l] == '.') l--;while(r <= n && g[i][r] == '.') r++;l = max(l, j - k);r = min(r, j + k);int u = i, d = i;while(u >= 1 && g[u][j] == '.') u--;while(d <= n && g[d][j] == '.') d++;u = max(u, i - k);d = min(d, i + k);int row = 0, col = 0;if(r - l - 1 >= k) row = r - l - k + 1;if(d - u - 1 >= k) col = d - u - k + 1;if(res <= row + col) {res = row + col;x = i;y = j;}}cout << x << ' ' << y << endl;return 0;
}