Skip to Content
CoursesCSC102การแก้ไขเมทริกซ์โดยตั้งค่าแถวและคอลัมน์เป็นศูนย์

การแก้ไขเมทริกซ์โดยตั้งค่าแถวและคอลัมน์เป็นศูนย์

โจทย์

เขียนโปรแกรมที่แก้ไขเมทริกซ์ขนาด m x n โดยถ้ามีสมาชิกใดในเมทริกซ์เป็น 0 ให้ตั้งค่าทั้งแถวและคอลัมน์ที่มีสมาชิกนั้นเป็น 0 ทั้งหมด โปรแกรมควรทำการแก้ไขนี้แบบ in-place หมายความว่าต้องปรับปรุงเมทริกซ์เดิมโดยไม่ใช้พื้นที่เก็บข้อมูลเมทริกซ์เพิ่มเติม

ข้อมูลนำเข้าคือตัวเมทริกซ์เอง ซึ่งอาจประกอบด้วยจำนวนเต็มทั้งบวกและลบ และผลลัพธ์ควรเป็นเมทริกซ์ที่ถูกแก้ไขแล้ว โดยทุกแถวและคอลัมน์ที่มี 0 ได้ถูกตั้งค่าเป็น 0 ทั้งหมด

ตัวอย่าง: เมทริกซ์ขนาด 3 x 3

Input=[111101111]Input = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix} Output=[101000101]Output = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix}

InputOutput
3 3
1 1 1
1 0 1
1 1 1		1 0 1
0 0 0
1 0 1

โค้ด

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int m = scanner.nextInt();
        int n = scanner.nextInt();
 
        int[][] matrix = new int[m][n];
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }
 
        boolean firstRowZero = false, firstColZero = false;
 
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }
 
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
 
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
 
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
 
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
 
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
 
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

คำอธิบาย

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int m = scanner.nextInt();
        int n = scanner.nextInt();
 
        int[][] matrix = new int[m][n];
 
        // ลูปที่ 1: รับข้อมูลเมทริกซ์
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

ลูปที่ 1 เป็นลูปซ้อนที่ใช้ในการรับข้อมูลเมทริกซ์จากผู้ใช้:

  • ลูปภายนอก (i) วนซ้ำตามจำนวนแถว (m)
  • ลูปภายใน (j) วนซ้ำตามจำนวนคอลัมน์ (n)
  • ในแต่ละรอบ เราอ่านค่าจำนวนเต็มและเก็บไว้ในตำแหน่งที่เหมาะสมในเมทริกซ์
        boolean firstRowZero = false, firstColZero = false;
 
        // ลูปที่ 2: ตรวจสอบแถวแรก
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }
 
        // ลูปที่ 3: ตรวจสอบคอลัมน์แรก
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }

ลูปที่ 2 และ 3 ใช้ในการตรวจสอบว่าแถวแรกและคอลัมน์แรกมี 0 หรือไม่:

  • ลูปที่ 2 วนซ้ำตามคอลัมน์ของแถวแรก ถ้าพบ 0 จะตั้งค่า firstRowZero เป็น true และออกจากลูป
  • ลูปที่ 3 วนซ้ำตามแถวของคอลัมน์แรก ถ้าพบ 0 จะตั้งค่า firstColZero เป็น true และออกจากลูป
        // ลูปที่ 4: ใช้แถวแรกและคอลัมน์แรกเป็นตัวบ่งชี้
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

ลูปที่ 4 เป็นลูปซ้อนที่ใช้แถวแรกและคอลัมน์แรกเป็นตัวบ่งชี้:

  • ลูปภายนอก (i) เริ่มจาก 1 ถึง m-1
  • ลูปภายใน (j) เริ่มจาก 1 ถึง n-1
  • ถ้าพบ 0 ในตำแหน่ง (i, j) เราจะตั้งค่าสมาชิกแรกของแถว i และคอลัมน์ j เป็น 0
        // ลูปที่ 5: ตั้งค่าแถวเป็น 0
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
 
        // ลูปที่ 6: ตั้งค่าคอลัมน์เป็น 0
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }

ลูปที่ 5 และ 6 ใช้ในการตั้งค่าแถวและคอลัมน์เป็น 0 ตามตัวบ่งชี้:

  • ลูปที่ 5 ตรวจสอบแต่ละแถว ถ้าสมาชิกแรกของแถวเป็น 0 จะตั้งค่าทุกสมาชิกในแถวนั้นเป็น 0
  • ลูปที่ 6 ตรวจสอบแต่ละคอลัมน์ ถ้าสมาชิกแรกของคอลัมน์เป็น 0 จะตั้งค่าทุกสมาชิกในคอลัมน์นั้นเป็น 0
        // ลูปที่ 7 และ 8: จัดการกับแถวแรกและคอลัมน์แรก
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
 
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }

ลูปที่ 7 และ 8 ใช้ในการจัดการกับแถวแรกและคอลัมน์แรก:

  • ถ้า firstRowZero เป็น true ลูปที่ 7 จะตั้งค่าทุกสมาชิกในแถวแรกเป็น 0
  • ถ้า firstColZero เป็น true ลูปที่ 8 จะตั้งค่าทุกสมาชิกในคอลัมน์แรกเป็น 0
        // ลูปที่ 9: แสดงผลลัพธ์
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

ลูปที่ 9 เป็นลูปซ้อนที่ใช้ในการแสดงผลลัพธ์:

  • ลูปภายนอก (i) วนซ้ำตามจำนวนแถว
  • ลูปภายใน (j) วนซ้ำตามจำนวนคอลัมน์
  • ในแต่ละรอบ เราพิมพ์ค่าของสมาชิกในเมทริกซ์ โดยเว้นวรรคระหว่างแต่ละค่า
  • หลังจากพิมพ์ครบทุกคอลัมน์ในแถว เราขึ้นบรรทัดใหม่

โค้ดนี้ใช้เทคนิคการใช้แถวแรกและคอลัมน์แรกเป็นตัวบ่งชี้ ทำให้สามารถแก้ไขเมทริกซ์ได้โดยไม่ต้องใช้หน่วยความจำเพิ่มเติม ซึ่งเป็นวิธีที่มีประสิทธิภาพในการแก้ปัญหานี้

หลักการทำงาน

ปรับปรุงล่าสุด