This problem asks to choose a good implementation approach. Depending on your choice, it will be very difficult to implement.

The writer’s solution focus on the following fact.

• Every cross contains a cross of size \(1\) at its center.
• Conversely, the sub-occurrence of #s in a cross of size \(1\) only occurs at the center of a cross of size \(1\) or greater.

Simply put, we detect a cross by first searching fro the following pattern:

#.#
.#.
#.#

For example, in the first figure in the problem statement, we can find a cross at \((i, j) = (2, 2), (7, 3)\), but not at any other places.

Focusing on a cross of size \(1\), we can find the answer with the following algorithm.

• Let \(\mathrm{ans}\) be an array, initially filled with 0.
• For each pair \((i, j)\) such that \(1 \leq i \leq H, 1 \leq j \leq W\), do the following:
  • Check if \((i, j), (i+1,j+1), (i+1,j-1), (i-1,j+1)\) and \((i-1,j-1)\) have #. If any of them has ., terminate the operation.
  • If the five are all #, it is a size-\(1\) cross that is a part of a cross. Find the size of the cross centered at \((i, j)\) using a for loop.
  • Increment \(\mathrm{ans}[d]\) by \(1\), where \(d\) is the size of the cross centered at \((i, j)\).
• The answer is \(\mathrm{ans}[1], \mathrm{ans}[2], \dots, \mathrm{ans}[N]\) when everything is done.

The complexity is about \(\mathrm{O}(HW)\), which is fast enough.

• Sample code (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];
}