Bài 24.1. Tổng Cường Độ Hình Đồng Hồ Cát Lớn Nhất - [Độ khó: Khá]

Một nhóm nghiên cứu địa chất đang phân tích dữ liệu địa chấn dưới lòng đất, được biểu diễn dưới dạng một ma trận các giá trị cường độ. Họ nhận thấy rằng các cấu trúc địa chất đặc biệt thường tạo ra các mẫu hình "đồng hồ cát" trong dữ liệu. Một hình đồng hồ cát được định nghĩa là một cấu trúc 3x3 bao gồm 7 ô: ba ô ở hàng đầu tiên, một ô ở giữa hàng thứ hai, và ba ô ở hàng thứ ba. Ví dụ:

A B C
  D
E F G

Nhiệm vụ của bạn là giúp họ tìm ra vị trí của hình đồng hồ cát có tổng cường độ lớn nhất trong toàn bộ lưới dữ liệu.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên dương N và M (3 <= N, M <= 200), lần lượt là số hàng và số cột của ma trận. N dòng tiếp theo, mỗi dòng chứa M số nguyên A[i][j] (-1000 <= A[i][j] <= 1000), biểu diễn giá trị cường độ của từng ô.

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng cường độ lớn nhất tìm được của một hình đồng hồ cát.

Ví dụ:

Input:

4 5
-9 -9 -9  1  1
 0 -9  0  4  3
-9 -9 -9  1  1
 0  0  0  0  0

Output:

4

Giải thích:

• Ma trận có kích thước 4x5. Chúng ta cần tìm hình đồng hồ cát 3x3.
• Có thể có nhiều hình đồng hồ cát khác nhau trong ma trận.
• Xét hình đồng hồ cát với đỉnh trên cùng bên trái tại (0, 0):

  -9 -9 -9
     -9
  -9 -9 -9

  Tổng: (-9) + (-9) + (-9) + (-9) + (-9) + (-9) + (-9) = -63
• Xét hình đồng hồ cát với đỉnh trên cùng bên trái tại (0, 1):

  -9 -9  1
     0
  -9 -9  1

  Tổng: (-9) + (-9) + 1 + 0 + (-9) + (-9) + 1 = -34
• Xét hình đồng hồ cát với đỉnh trên cùng bên trái tại (0, 2):

  -9  1  1
     4
  -9  1  1

  Tổng: (-9) + 1 + 1 + 4 + (-9) + 1 + 1 = -10
• Xét hình đồng hồ cát với đỉnh trên cùng bên trái tại (1, 1):

  -9  0  4
     -9
   0  0  0

  Tổng: (-9) + 0 + 4 + (-9) + 0 + 0 + 0 = -14
• ...

• Hình đồng hồ cát có tổng lớn nhất là 4, được tạo bởi các ô sau:

  (0,3) (0,4) (0,5) -> (0,3) (0,4) (INVALID)
  (1,3)
  (2,3) (2,4) (2,5) -> (2,3) (2,4) (INVALID)

  Sửa lại vị trí: Hình đồng hồ cát với đỉnh trên cùng bên trái tại (0, 2):

   -9  1  1
      4
   -9  1  1

  Tổng: (1) + (1) + (INVALID) + (4) + (1) + (1) + (INVALID). Phải nhìn kỹ ví dụ: Input:

  -9 -9 -9  1  1  (Hàng 0)
   0 -9  0  4  3  (Hàng 1)
  -9 -9 -9  1  1  (Hàng 2)
   0  0  0  0  0  (Hàng 3)

  Một hình đồng hồ cát có các phần tử: A[i][j], A[i][j+1], A[i][j+2], A[i+1][j+1], A[i+2][j], A[i+2][j+1], A[i+2][j+2]. Xét i=0, j=2:

  • Hàng 0: A[0][2] (-9), A[0][3] (1), A[0][4] (1)
  • Hàng 1: A[1][3] (4)
  • Hàng 2: A[2][2] (-9), A[2][3] (1), A[2][4] (1) Tổng = (-9) + 1 + 1 + 4 + (-9) + 1 + 1 = -10.

  Đây không phải 4. Xem lại ví dụ. Vùng 1 1 ở hàng 0, 4 ở hàng 1, 1 1 ở hàng 2. Vị trí đồng hồ cát cho ra kết quả 4 là tại A[0][3]: Các ô là: A[0][3] (1), A[0][4] (1) A[1][3] (4) A[2][3] (1), A[2][4] (1) Các ô bị thiếu là A[0][2] và A[2][2]. Ồ, tôi đã hiểu sai ví dụ. Dữ liệu đầu vào:

  -9 -9 -9  1  1   (Hàng 0, Cột 0 đến 4)
   0 -9  0  4  3   (Hàng 1)
  -9 -9 -9  1  1   (Hàng 2)
   0  0  0  0  0   (Hàng 3)

  Để có tổng 4, hình đồng hồ cát phải là:

     1  1   (A[0][3], A[0][4])
       4    (A[1][3])
     1  1   (A[2][3], A[2][4])

  Nhưng đây chỉ là 5 ô, không phải 7 ô. Một hình đồng hồ cát 3x3 có 7 ô. Có lẽ ví dụ này là một phần của ma trận lớn hơn, hoặc tôi đã hiểu sai về định nghĩa "hình đồng hồ cát". Định nghĩa chuẩn của Hourglass là 3x3 với 2 ô ở giữa hàng trên và dưới bị bỏ qua:

  A B C
    D
  E F G

  Cells: (r, c), (r, c+1), (r, c+2)

      (r+1, c+1)
      (r+2, c), (r+2, c+1), (r+2, c+2)

  Example:

  -9 -9 -9
     -9
  -9 -9 -9

  This is from (0,0): A[0][0], A[0][1], A[0][2], A[1][1], A[2][0], A[2][1], A[2][2] Sum: -9 + -9 + -9 + -9 + -9 + -9 + -9 = -63

  Let's re-check all possible 3x3 hourglasses: Possible top-left corners (i, j) such that i+2 < N and j+2 < M. For N=4, M=5: i can be 0, 1. j can be 0, 1, 2. Total 2 * 3 = 6 hourglasses.

  1. Top-left (0, 0):

     -9 -9 -9
        -9
     -9 -9 -9

     Sum = -63.

  2. Top-left (0, 1):

     -9 -9  1
        0
     -9 -9  1

     Sum = A[0][1]+A[0][2]+A[0][3] + A[1][2] + A[2][1]+A[2][2]+A[2][3] Sum = -9 + -9 + 1 + 0 + -9 + -9 + 1 = -34

  3. Top-left (0, 2):

     -9  1  1
        4
     -9  1  1

     Sum = A[0][2]+A[0][3]+A[0][4] + A[1][3] + A[2][2]+A[2][3]+A[2][4] Sum = -9 + 1 + 1 + 4 + -9 + 1 + 1 = -10

  4. Top-left (1, 0):

      0 -9  0
         -9
      0  0  0

     Sum = A[1][0]+A[1][1]+A[1][2] + A[2][1] + A[3][0]+A[3][1]+A[3][2] Sum = 0 + -9 + 0 + -9 + 0 + 0 + 0 = -18

  5. Top-left (1, 1):

     -9  0  4
        1
      0  0  0

     Sum = A[1][1]+A[1][2]+A[1][3] + A[2][2] + A[3][1]+A[3][2]+A[3][3] Sum = -9 + 0 + 4 + -9 + 0 + 0 + 0 = -14. (Correction: A[2][2] is -9, but for (1,1) hourglass, A[2][2] is in the middle of third row. This is A[2][2], A[2][3], A[2][4] for (1,1) hourglass. A[2][2] is -9, A[2][3] is 1, A[2][4] is 1. A[3][1] is 0, A[3][2] is 0, A[3][3] is 0. Ah, I used A[3][1], A[3][2], A[3][3] instead of A[3][0], A[3][1], A[3][2] No, my general sum logic for (r,c) is A[r][c], A[r][c+1], A[r][c+2], A[r+1][c+1], A[r+2][c], A[r+2][c+1], A[r+2][c+2]. So for (1,1): A[1][1] (-9), A[1][2] (0), A[1][3] (4) A[2][2] (-9) A[3][1] (0), A[3][2] (0), A[3][3] (0) Sum = -9 + 0 + 4 + -9 + 0 + 0 + 0 = -14. This is correct.

  6. Top-left (1, 2):

      0  4  3
         1
      0  0  0

     Sum = A[1][2]+A[1][3]+A[1][4] + A[2][3] + A[3][2]+A[3][3]+A[3][4] Sum = 0 + 4 + 3 + 1 + 0 + 0 + 0 = 8

  Maximum sum found is 8. The example output is 4. This means the example's definition of hourglass is different or there's a typo in the output. Given "Mảng 2 Chiều trong C++ Medium" and the example, I'll stick to the common hourglass definition. It's possible the example used an outdated matrix or a slightly different problem definition. I will correct the example output to 8, as it reflects the most common "hourglass" definition.

  Corrected Explanation:

  • Ma trận có kích thước 4x5. Chúng ta cần tìm hình đồng hồ cát 3x3.
  • Một hình đồng hồ cát được tạo bởi 7 ô: A[r][c], A[r][c+1], A[r][c+2], A[r+1][c+1], A[r+2][c], A[r+2][c+1], A[r+2][c+2].
  • Có tổng cộng (N-2) * (M-2) hình đồng hồ cát có thể có. Trong trường hợp này là (4-2) * (5-2) = 2 * 3 = 6 hình.
  • Ta xét tất cả các vị trí (r, c) khả dĩ (r từ 0 đến N-3, c từ 0 đến M-3) và tính tổng cho từng hình đồng hồ cát:
    • Tại (r=0, c=0): (-9) + (-9) + (-9) + (-9) + (-9) + (-9) + (-9) = -63
    • Tại (r=0, c=1): (-9) + (-9) + 1 + 0 + (-9) + (-9) + 1 = -34
    • Tại (r=0, c=2): (-9) + 1 + 1 + 4 + (-9) + 1 + 1 = -10
    • Tại (r=1, c=0): 0 + (-9) + 0 + (-9) + 0 + 0 + 0 = -18
    • Tại (r=1, c=1): (-9) + 0 + 4 + (-9) + 0 + 0 + 0 = -14
    • Tại (r=1, c=2): 0 + 4 + 3 + 1 + 0 + 0 + 0 = 8
  • Tổng lớn nhất tìm được là 8.