## C - Cross Editorial by en_translator

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)\).

- Check if \((i, j), (i+1,j+1), (i+1,j-1), (i-1,j+1)\) and \((i-1,j-1)\) have
- 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];
}
```

posted:

last update: