Chênh lệch chỉ số lớn nhất (i,j) với A[i][j]=0 trong ma trận trong C++

Cho ma trận n×n. Nhiệm vụ: tìm chênh lệch chỉ số lớn nhất |i-j| tại các vị trí có giá trị 0. Điều kiện: ma trận có ít nhất một phần tử 0.

Ví dụ 1

Input

matrix = {{0, 1, 1},
          {0, 0, 0},
          {4, 5, 1}}

Output – Max difference = 1

Giải thích: Các vị trí có 0: (0,0), (1,0), (1,1), (1,2). Chênh lệch |i-j|: 0, 1, 0, 1. Max = 1.

Ví dụ 2

Input

matrix = {{0, 1, 1},
          {0, 2, 9},
          {4, 0, 1}}

Output – Max difference = 1

Giải thích: Vị trí 0: (0,0), (1,0), (2,1). Chênh lệch: 0, 1, 1. Max = 1.

Thuật toán

1. Nhập ma trận.
2. Khởi tạo max_val = 0.
3. Duyệt 2 vòng lặp i=0..n-1, j=0..n-1.
4. Nếu matrix[i][j] == 0: max_val = max(max_val, abs(i-j)).
5. Trả về max_val.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

#define ROW 3
#define COL 3

int maxDiffZero(int matrix[ROW][COL]) {
    int max_val = 0;
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (matrix[i][j] == 0) {
                max_val = max(max_val, abs(i - j));
            }
        }
    }
    return max_val;
}

int main() {
    int matrix[ROW][COL] = {
        {1, 2, 0},
        {0, 4, 0},
        {0, 1, 0}
    };
    cout << "Maximum difference of indices with A[i][j]=0: " 
         << maxDiffZero(matrix) << endl;
    return 0;
}

Kết quả

Maximum difference of indices with A[i][j]=0: 2

Giải thích: Vị trí 0: (0,2)→|0-2|=2, (1,0)→1, (1,2)→1, (2,0)→2, (2,2)→0. Max = 2.

Độ phức tạp: O(n²) - duyệt toàn bộ ma trận.