หาความต่างดัชนี (i,j) สูงสุดที่ A[i][j] = 0 ในเมทริกซ์ C++

ได้รับเมทริกซ์ขนาด n×n และเงื่อนไข a[i][j] = 0 งานคือหาความต่างของดัชนี |i - j| สูงสุดของตำแหน่งที่มีค่า 0

ตัวอย่าง

ตัวอย่างที่ 1

Input:

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

ตำแหน่งที่เป็น 0: (0,0), (1,0), (1,1), (1,2)

ความต่าง |i-j|: 0, 1, 0, 1

Output: 1

ตัวอย่างที่ 2

Input:

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

ตำแหน่งที่เป็น 0: (0,0), (1,0), (2,1)

ความต่าง |i-j|: 0, 1, 1

Output: 1

แนวทางแก้ปัญหา

1. รับเมทริกซ์ขนาด n×n (ต้องมี 0 อย่างน้อย 1 ตัว)
2. ตั้งค่า maxDiff = 0
3. วนลูป 2 ชั้น: i 0 ถึง n-1, j 0 ถึง n-1
4. ถ้า matrix[i][j] == 0 คำนวณ diff = abs(i - j)
5. อัปเดต maxDiff = max(maxDiff, diff)
6. คืนค่า maxDiff

ตัวอย่างโค้ด

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

int maxIndexDiffZero(const vector<vector<int>>& matrix) {
    int n = matrix.size();
    int maxDiff = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                maxDiff = max(maxDiff, abs(i - j));
            }
        }
    }
    return maxDiff;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 0},
        {0, 4, 0},
        {0, 1, 0}
    };
    
    cout << "Maximum index difference with A[i][j]=0: " 
         << maxIndexDiffZero(matrix) << endl;
    return 0;
}

ผลลัพธ์

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

ตำแหน่ง 0: (0,2)→|0-2|=2, (1,0)→1, (1,2)→1, (2,0)→2, (2,2)→0 → max = 2

โค้ดแบบอาร์เรย์ 2D แบบดิบ

#include <iostream>
#include <cstdlib>  // abs
using namespace std;

#define ROW 3
#define COL 3

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

int main() {
    int matrix[ROW][COL] = {
        {1, 2, 0},
        {0, 4, 0},
        {0, 1, 0}
    };
    cout << "Max diff: " << maximum(matrix) << endl;
    return 0;
}

ความซับซ้อน

• เวลา: O(n²) – ตรวจสอบทุกเซลล์ในเมทริกซ์ n×n
• พื้นที่: O(1) – ใช้ตัวแปรคงที่

ข้อสังเกต

• โจทย์ระบุ "maximum difference of indices" ซึ่งหมายถึง |i - j| (ค่าสัมบูรณ์)
• หากเมทริกซ์ไม่มี 0 เลย จะคืนค่า 0 (อาจต้องจัดการ error แยกต่างหาก)
• สามารถเพิ่มประสิทธิภาพได้โดยหา 0 ในแถวแรก/สุดท้าย และคอลัมน์แรก/สุดท้าย ก่อน เพราะให้ |i-j| มากที่สุด