// 2025-04-06 #include #include #include #include #define X first #define Y second using namespace std; int n; int dx[4] = { 1, -1, 0, 0 }; int dy[4] = { 0, 0, 1 ,-1 }; int board[22][22]; int partial[22][22]; int mn = 999999999; int sub; int nums[6]; queue> Q; void floodFill(int x, int y, int num) { Q.push({ x, y }); partial[x][y] = num; while (!Q.empty()) { auto cur = Q.front(); Q.pop(); for (int dir = 0; dir < 4; dir++) { int nx = cur.X + dx[dir]; int ny = cur.Y + dy[dir]; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if (partial[nx][ny] != 0) continue; Q.push({ nx, ny }); partial[nx][ny] = num; } } } void calc() { fill(nums, nums + 6, 0); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) nums[partial[i][j]] += board[i][j]; } void div(int x, int y, int d1, int d2) { fill(&partial[0][0], &partial[0][0] + 22 * 22, 0); for (int i = x, j = y; i <= x + d1 && j >= y - d1; i++, j--) for (int k = i, l = j; k <= i + d2 && l <= j + d2; k++, l++) partial[k][l] = 5; for (int i = x - 1; i >= 0; i--) partial[i][y] = 1; for (int j = y + d2 + 1; j < n; j++) partial[x + d2][j] = 2; for (int j = y - d1 - 1; j >= 0; j--) partial[x + d1][j] = 3; for (int i = x + d1 + d2 + 1; i < n; i++) partial[i][y - d1 + d2] = 4; floodFill(0, 0, 1); floodFill(0, n - 1, 2); floodFill(n - 1, 0, 3); floodFill(n - 1, n - 1, 4); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> board[i][j]; for (int i = 0; i < n - 2; i++) for (int j = 1; j < n - 1; j++) for (int d1 = 1; i + d1 < n && j - d1 > 0; d1++) for (int d2 = 1; i + d2 < n && j + d2 < n; d2++) { /* for (int x = 0; x < n; x++) { for (int y = 0; y < n; y++) { cout << partial[x][y] << ' '; } cout << '\n'; } cout << '\n'; */ div(i, j, d1, d2); calc(); nums[5] += nums[0]; sub = *max_element(nums + 1, nums + 6) - *min_element(nums + 1, nums + 6); mn = min(mn, sub); } cout << mn; return 0; }

제출 #50072

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: