Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
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 , its bounding box must be . The blob must contain exactly 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 , centered at . The frame consists exactly of the cells with Manhattan distance from the center. So a blob is a valid diagonal square iff is odd, its size is with , and every cell satisfies .
Run flood-fill (DFS/BFS) in 8 directions to extract each component. Let , , and be the component size.
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.
Suppose a component has bounding box rows and columns . Let
For an axis-aligned square frame of side :
Because the number of border cells is exactly , 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.
A diagonal square of size () is a diamond: the set of cells at Manhattan distance from a center cell . Its bounding box is a square, so:
Again, there are exactly 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.
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.
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 cells the running time is , and the memory consumption is . With 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;
}