この問題は上手な実装方針を選ぶことができるかを聞いている問題です。バツ印の特徴をつかんだ実装方針を選ばないと場合によっては実装が大変になると思います。

想定解は次の事実に注目しています。

• すべてのバツ印は、中央にサイズ \(1\) の部分的なバツ印を含んでる。
• 逆に、サイズ \(1\) の部分的なバツ印の # の配置は、サイズ \(1\) 以上のバツ印の中央でしか登場しない。

ここで「サイズ \(1\) の部分的なバツ印」というのは、砕けた言い方をすると、

#.#
.#.
#.#

が部分的に登場する箇所に注目してバツ印を検出するということです。例えば 問題文に載っている図(下図) では \((i, j) = (2, 2), (7, 3)\) にサイズ \(1\) の部分的なバツ印が登場していて、これ以外にはバツ印は存在しません。

サイズ \(1\) のバツ印に注目すると、次のようなアルゴリズムで答えを求めることができます。

• \(\mathrm{ans}\) を答えを管理する 0 初期化された配列とする。
• \(1 \leq i \leq H, 1 \leq j \leq W\) を満たす \((i, j)\) の組について次の操作を行う。
  • \((i, j), (i+1,j+1), (i+1,j-1), (i-1,j+1),(i-1,j-1)\) に # が置かれているかを判定する。どこか 1 ヵ所でも . である場合は操作を終了する。
  • 上記の \(5\) ヵ所が全て # であるとき、サイズ \(1\) のバツ印が部分的に登場していることになる。この場合、\((i, j)\) を中心とするバツ印のサイズを for-loop を用いて計算する。
  • \((i, j)\) を中心とするバツ印のサイズを \(d\) として、\(\mathrm{ans}[d]\) に \(1\) を加える。
• 操作を終了した時点での \(\mathrm{ans}[1], \mathrm{ans}[2], \dots, \mathrm{ans}[N]\) が答えである。

計算量は \(\mathrm{O}(HW)\) 程度で、十分高速です。

• 実装例(C++)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> g(H);
  for (auto& x : g) cin >> x;

  auto ok = [&](int i, int j) { return 0 <= i and i < H and 0 <= j and j < W; };
  auto test = [&](int i, int j, int d) {
    for (auto& x : vector{+d, -d}) {
      for (auto& y : vector{+d, -d}) {
        int s = i + x, t = j + y;
        if (!ok(s, t) or g[s][t] != '#') return false;
      }
    }
    return true;
  };

  int N = min(H, W);
  vector<int> ans(N + 1);
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (g[i][j] != '#') continue;
      if (test(i, j, 1)) {
        int d = 1;
        while (test(i, j, d + 1)) d++;
        ans[d]++;
      }
    }
  }
  for (int i = 1; i <= N; i++) cout << ans[i] << " \n"[i == N];
}