#include #include #include #define x first #define y second using namespace std; int b[100][100]; int dist[100][100]; int island[100][100]; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> b[i][j]; } } for (int i = 0 ; i < n ;i ++) fill_n(dist[i], n ,-1); queue> q, e; int cnt = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (b[i][j] && dist[i][j] == -1) { q.emplace(i, j); dist[i][j] = 0; while (!q.empty()) { auto [fst, snd] = q.front(); q.pop(); for (int d = 0;d < 4; d++) { int nx = fst + dx[d], ny = snd + dy[d]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (dist[nx][ny] != -1) continue; if (b[nx][ny]) { dist[nx][ny] = 0; q.emplace(nx, ny); } else { dist[nx][ny] = 1; e.emplace(nx, ny); } island[nx][ny] = cnt; } } cnt++; } } } int ans = 1e9+7; while (!e.empty()) { auto [cx, cy] = e.front(); e.pop(); for (int d = 0;d < 4; d++) { int nx = cx + dx[d], ny = cy + dy[d]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (island[nx][ny] == 0) { island[nx][ny] = island[cx][cy]; dist[nx][ny] = dist[cx][cy] + 1; q.emplace(nx, ny); } else if (island[nx][ny] != island[cx][cy]) { ans = min(ans, dist[cx][cy] + dist[nx][ny]); } } } cout << ans; return 0; }

제출 #128591

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: