#include #include #include using namespace std; queue> q; int n, re, t[111][111], k[111][111], ch[111][111], p[11111]; int d[11] = { 1, 0, -1, 0, 1 }; int fi(int x) { if (p[x] == x) return x; return p[x] = fi(p[x]); } void uni(int x, int y) { x = fi(x), y = fi(y); if (x != y) p[y] = x; } int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { cin >> t[i][j]; p[i * n + j] = i * n + j; if (t[i][j]) { q.push({ i, j }); ch[i][j] = 1; for (int l = 0; l < 4; ++l) { int tx = i + d[l], ty = j + d[l + 1]; if (tx > 0 && tx <= n && ty > 0 && ty <= n && t[tx][ty]) uni(i * n + j, tx * n + ty); } } } } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; ++i) { int tx = x + d[i], ty = y + d[i + 1]; if (tx > 0 && tx <= n && ty > 0 && ty <= n) { int a = x * n + y, b = tx * n + ty; if (!ch[tx][ty]) { uni(a, b); ch[tx][ty] = 1; k[tx][ty] = k[x][y] + 1; q.push({ tx, ty }); } else if (fi(a) != fi(b)) { re = k[tx][ty] + k[x][y]; break; } } } if (re) break; } cout << re; }

제출 #117953

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: