11CUnreviewed2200Kimi K2.6 (thinking)

How Many Squares?

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

implementation

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

The condition “can’t touch any foreign 1” is extremely restrictive. If you look at a valid square as a set of cells, what can you say about its neighbors?

Work in 8-directional connectivity. If a square frame were adjacent to any other 1, that 1 would belong to the same connected blob. Hence every valid square is an entire 8-connected component of 1s, and every 8-connected component can contain at most one square.

For a blob to be an axis-aligned square frame of side $k$ , its bounding box must be $k \times k$ . The blob must contain exactly $4(k-1)$ cells, and every one of those cells must lie on the border of that bounding box.

For a diagonal square, think of a diamond. Its bounding box is a square of odd side $2d+1$ , centered at $(r_c,c_c)$ . The frame consists exactly of the cells with Manhattan distance $d$ from the center. So a blob is a valid diagonal square iff $h=w$ is odd, its size is $4d$ with $d=(h-1)/2$ , and every cell satisfies $|r-r_c|+|c-c_c|=d$ .

Run flood-fill (DFS/BFS) in 8 directions to extract each component. Let $h=\max r-\min r+1$ , $w=\max c-\min c+1$ , and $s$ be the component size.

Axis: $h=w$ , $s=4(h-1)$ , and each cell is on the bounding-box border.
Diagonal: $h=w$ odd, $d=(h-1)/2$ , $s=4d$ , and each cell obeys $|r-r_c|+|c-c_c|=d$ . Count a component if it passes either test.

The key observation

Because a square cannot touch a foreign 1 by side or corner, no cell outside the square may be 8-adjacent to any of its cells. Consequently the set of cells forming a valid square is an entire 8-connected component of 1s. Conversely, any 8-connected component that happens to be shaped exactly like a square frame is a valid answer. So the problem becomes:

Find all 8-connected components of 1s and test whether each component is an axis-aligned square frame or a diagonal (diamond) square frame.

Axis-aligned check

Suppose a component has bounding box rows $[r_1,r_2]$ and columns $[c_1,c_2]$ . Let

h = r_2-r_1+1,\qquad w = c_2-c_1+1,\qquad s = \text{component size}.

For an axis-aligned square frame of side $k$ :

the bounding box must be a square: $h = w = k$ ;
the component must contain all border cells of that box, and no others. A $k\times k$ box has exactly $4(k-1)$ border cells, so we need $s = 4(k-1)$ ;
every cell of the component must satisfy $r=r_1$ or $r=r_2$ or $c=c_1$ or $c=c_2$ .

Because the number of border cells is exactly $4(k-1)$ , the size test together with the “every cell is on the border” test guarantees that the component is the complete frame—no missing corners, no protrusions.

Diagonal check

A diagonal square of size $k$ ( $k\ge 2$ ) is a diamond: the set of cells at Manhattan distance $d=k-1$ from a center cell $(r_c,c_c)$ . Its bounding box is a $(2d+1)\times(2d+1)$ square, so:

$h = w$ and $h$ is odd;
let $d = (h-1)/2$ ;
a diamond perimeter contains exactly $4d$ cells, so we need $s = 4d$ ;
the center is $(r_c,c_c) = (r_1+d,\; c_1+d)$ , and every component cell must satisfy

|r-r_c| + |c-c_c| = d.

Again, there are exactly $4d$ integer solutions to this equation inside the bounding box, so the size test plus the Manhattan-distance test forces the component to be the full diamond perimeter.

Why nested squares are not a problem

A large square frame may contain smaller frames deep in its interior. Those interior frames are 8-connected components on their own because the layer of cells immediately adjacent to the outer frame must be 0. Our algorithm simply counts each component independently, so nested squares are handled automatically.

Complexity analysis

Each cell is visited once during flood-fill and inspected a constant number of times during the geometric tests. Hence for a test case with $n\cdot m$ cells the running time is $O(n m)$ , and the memory consumption is $O(n m)$ . With $\sum n m \le 10^6$ this easily satisfies the limits.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();
    int T;
    if (!(cin >> T)) return 0;
    const int dr[8] = {-1,-1,-1,0,0,1,1,1};
    const int dc[8] = {-1,0,1,-1,1,-1,0,1};
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<string> g(n);
        for (int i = 0; i < n; ++i) cin >> g[i];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (g[i][j] == '0') continue;
                vector<pair<int,int>> comp;
                vector<pair<int,int>> st;
                st.emplace_back(i, j);
                g[i][j] = '0';
                int mnR = i, mxR = i, mnC = j, mxC = j;
                while (!st.empty()) {
                    auto [r, c] = st.back();
                    st.pop_back();
                    comp.emplace_back(r, c);
                    mnR = min(mnR, r);
                    mxR = max(mxR, r);
                    mnC = min(mnC, c);
                    mxC = max(mxC, c);
                    for (int d = 0; d < 8; ++d) {
                        int nr = r + dr[d];
                        int nc = c + dc[d];
                        if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                        if (g[nr][nc] == '0') continue;
                        g[nr][nc] = '0';
                        st.emplace_back(nr, nc);
                    }
                }
                int sz = (int)comp.size();
                if (sz < 4) continue;
                int h = mxR - mnR + 1;
                int w = mxC - mnC + 1;
                bool ok = false;
                // axis-aligned square
                if (h == w) {
                    int k = h;
                    if (sz == 4 * (k - 1)) {
                        bool good = true;
                        for (auto [r, c] : comp) {
                            if (r != mnR && r != mxR && c != mnC && c != mxC) {
                                good = false;
                                break;
                            }
                        }
                        if (good) {
                            ++ans;
                            ok = true;
                        }
                    }
                }
                // diagonal square
                if (!ok && h == w && (h % 2 == 1)) {
                    int d = (h - 1) / 2;
                    if (sz == 4 * d) {
                        int rc = mnR + d;
                        int cc = mnC + d;
                        bool good = true;
                        for (auto [r, c] : comp) {
                            if (abs(r - rc) + abs(c - cc) != d) {
                                good = false;
                                break;
                            }
                        }
                        if (good) ++ans;
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();
    int T;
    if (!(cin >> T)) return 0;
    const int dr[8] = {-1,-1,-1,0,0,1,1,1};
    const int dc[8] = {-1,0,1,-1,1,-1,0,1};
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<string> g(n);
        for (int i = 0; i < n; ++i) cin >> g[i];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (g[i][j] == '0') continue;
                vector<pair<int,int>> comp;
                vector<pair<int,int>> st;
                st.emplace_back(i, j);
                g[i][j] = '0';
                int mnR = i, mxR = i, mnC = j, mxC = j;
                while (!st.empty()) {
                    auto [r, c] = st.back();
                    st.pop_back();
                    comp.emplace_back(r, c);
                    mnR = min(mnR, r);
                    mxR = max(mxR, r);
                    mnC = min(mnC, c);
                    mxC = max(mxC, c);
                    for (int d = 0; d < 8; ++d) {
                        int nr = r + dr[d];
                        int nc = c + dc[d];
                        if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                        if (g[nr][nc] == '0') continue;
                        g[nr][nc] = '0';
                        st.emplace_back(nr, nc);
                    }
                }
                int sz = (int)comp.size();
                if (sz < 4) continue;
                int h = mxR - mnR + 1;
                int w = mxC - mnC + 1;
                bool ok = false;
                // axis-aligned square
                if (h == w) {
                    int k = h;
                    if (sz == 4 * (k - 1)) {
                        bool good = true;
                        for (auto [r, c] : comp) {
                            if (r != mnR && r != mxR && c != mnC && c != mxC) {
                                good = false;
                                break;
                            }
                        }
                        if (good) {
                            ++ans;
                            ok = true;
                        }
                    }
                }
                // diagonal square
                if (!ok && h == w && (h % 2 == 1)) {
                    int d = (h - 1) / 2;
                    if (sz == 4 * d) {
                        int rc = mnR + d;
                        int cc = mnC + d;
                        bool good = true;
                        for (auto [r, c] : comp) {
                            if (abs(r - rc) + abs(c - cc) != d) {
                                good = false;
                                break;
                            }
                        }
                        if (good) ++ans;
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

View on Codeforces Back to the list