လိမ္မော်သီးအားလုံးပုပ်ပျက်ရန်လိုအပ်သောအနည်းဆုံးအချိန်



မကြာခဏမေးတယ် Adobe က အမေဇုံ ဘလွန်းဘာ့ဂ် Microsoft က
အခင်းအကျင်း အနံပထမရှာဖွေရေး matrix

ပြProbleနာဖော်ပြချက်

“ လိမ္မော်သီးများအားလုံးပုပ်ပျက်စေရန်လိုအပ်သောအနည်းဆုံးအချိန်” ပြproblemနာကသင့်အားက 2D ခင်းကျင်းခြင်း, ဆဲလ်တိုင်းဖြစ်နိုင်သောတန်ဖိုးများသုံးခုထဲကတစ်ခုရှိပါတယ် 0, 1 သို့မဟုတ် 2 ။
0 ကဗလာဆဲလ်ကိုဆိုလိုသည်။
1 ဆိုသည်မှာလတ်ဆတ်သောလိမ္မော်ရောင်ကိုဆိုလိုသည်။
2 ပုပ်နေသောလိမ္မော်ရောင်ကိုဆိုလိုသည်။
အကယ်၍ လိမ္မော်ရောင်သည်လိမ္မော်သီးတစ်လုံးကို ၁ ခုယူနစ်ဖြင့်ပုပ်နိုင်လျှင်လိမ္မော်သီးအားလုံးကိုပုပ်ရန်အချိန်ယူပါ။

ဥပမာ

{
{0, 1, 1}
{2, 1, 2}
{1, 0, 1}
}
2
{
{0, 1, 0}
{2, 0, 2}
{1, 1, 1}
{1, 1, 1}
}
-1

လိမ္မော်သီးအားလုံးပုပ်ပျက်ရန်လိုအပ်သောအနည်းဆုံးအချိန်ကိုရှာဖွေရန် Algorithm ကို

အားလုံးသောပုပ်နေသောလိမ္မော်များသည်အစမှတ်များဖြစ်ပြီး၎င်းတို့သည်ကပ်လျက်ရှိလတ်ဆတ်သောလိမ္မော်များကို ၁ ယူနစ်ဖြင့်ပုပ်ပျက်စေသည်။ ကျွန်ုပ်တို့လုပ်နိုင်သည့်လိမ္မော်သီးများအားလုံးပုပ်ပျက်ရန်လိုအပ်သောစုစုပေါင်းအချိန်ကိုရှာဖွေရန် အနံ - ပထမရှာဖွေရေး(BFS) ပုပ်နေသောလိမ္မော်သီးများအားလုံးကို BFS ၏အစအဖြစ်ယူဆသည်။

  1. တစ်ဦး Create ဆံပင်ကြိုး ၏လိုအပ်သောဆဲလ်များ၏သြဒီနိတ်ကိုသိုလှောင်ရန်၊ ကိုသြဒီနိတ်များ၊ ဆိုလိုသည်မှာလူတန်းစားသည်ပုံစံ (row, col) ၏ဒေတာများကိုသိမ်းဆည်းထားသင့်သည်။ 0 အဖြစ် variable တစ်ခုအချိန် Initialize ။
  2. ပေးထားသော matrix တွင် ဖြတ်၍ ပုပ်နေသောလိမ္မော်သီးများ၏သြဒီနိတ်များကိုတန်းထဲသို့ထည့်ပါ။
  3. အဆိုပါတန်းစီအချည်းနှီးသောထပ်အဆင့် 4 မဟုတ်နေစဉ်။
  4. Variable အရွယ်ကိုလူတန်း၏အရွယ်အနေနှင့်စတင်ပါ။ i သည် 0 မှအရွယ်အစား (မပါ ၀ င်ပါ) အတွက် loop ကို run ပါ။ တိုင်းတာမှုတိုင်း၌ element တစ်ခုမှ element တစ်ခုထွက်ပါ။ ၎င်း၏ကပ်လျက်နှစ်ဖက်တွင်လိမ္မော်ရောင်အသစ် (ဘယ်၊ ညာ၊ အပေါ်နှင့်အောက်) ရှိလျှင်လိမ္မော်ရောင်၏သြဒီနိတ်များကိုတန်းစီရန်တွန်းပြီး၎င်းလိမ္မော်ရောင်ကိုပုပ်နေသကဲ့သို့မှတ်သားပါ။ လတ်ဆတ်သောလိမ္မော်သီးအချို့ရှိပါကအချိန်ကိုတစ်ယူနစ်တိုးနိုင်သည်။
  5. ယခု matrix တွင်လိမ္မော်ရောင်လတ်ဆတ်နေဆဲရှိမရှိစစ်ဆေးပါ၊ အကယ်၍ ဟုတ်ကဲ့၊ လိမ္မော်သီးအားလုံးပုပ်ပျက်သွားနိုင်လျှင် -1 သို့ပြန်သွားပါ။

ရှင်းလင်းချက်

ဥပမာကိုသုံးသပ်ကြည့်ပါ။
{
{0, 1, 1}
{2, 1, 2}
{1, 0, 1}
}

လိမ္မော်သီးအားလုံးပုပ်ပျက်ရန်လိုအပ်သောအနည်းဆုံးအချိန်

လိမ္မော်သီးအားလုံးသည်အချိန်တွင် ၂ ပုပ်နေသည်။

ကုဒ်

လိမ္မော်သီးအားလုံးပုပ်ပျက်ရန်အနည်းဆုံးအချိန်ရှာရန် Java ကုဒ်

import java.util.LinkedList;
import java.util.Queue;

class MinimumTimeRequiredToRotAllOranges {
    private static int minTimeToRot(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;

        // create a queue to store coordinates
        Queue<Coordinate> queue = new LinkedList<>();
        // initialize a variable time as 0
        int time = 0;

        // Add all the rotten oranges coordinates to the queue
        // these acts as the starting point of the BFS
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 2) {
                    queue.add(new Coordinate(i, j));
                }
            }
        }

        while (!queue.isEmpty()) {
            // initialise size as size of queue
            int size = queue.size();
            // boolean variable representing whether or not an orange
            // is rotten in this time unit
            boolean isSomeFreshRotten = false;
            for (int i = 0; i < size; i++) {
                // remove an element from the queue
                Coordinate curr = queue.poll();

                // generate the coordinates of adjacent cells
                // if the generated coordinates are valid and there is a fresh orange
                // add the generated coordinates to the queue and mark that orange as rotten

                // left adjacent
                int leftRow = curr.row - 1;
                int leftCol = curr.col;
                if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
                    if (mat[leftRow][leftCol] == 1) {
                        queue.add(new Coordinate(leftRow, leftCol));
                        mat[leftRow][leftCol] = 2;
                        isSomeFreshRotten = true;
                    }
                }

                // right adjacent
                int rightRow = curr.row + 1;
                int rightCol = curr.col;
                if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
                    if (mat[rightRow][rightCol] == 1) {
                        queue.add(new Coordinate(rightRow, rightCol));
                        mat[rightRow][rightCol] = 2;
                        isSomeFreshRotten = true;
                    }
                }

                // up adjacent
                int upRow = curr.row;
                int upCol = curr.col + 1;
                if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
                    if (mat[upRow][upCol] == 1) {
                        queue.add(new Coordinate(upRow, upCol));
                        mat[upRow][upCol] = 2;
                        isSomeFreshRotten = true;
                    }
                }

                // down adjacent
                int downRow = curr.row;
                int downCol = curr.col - 1;
                if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
                    if (mat[downRow][downCol] == 1) {
                        queue.add(new Coordinate(downRow, downCol));
                        mat[downRow][downCol] = 2;
                        isSomeFreshRotten = true;
                    }
                }
            }

            // if there is some oranges rotten in this time unit,
            // increment time else end the BFS here
            if (isSomeFreshRotten)
                time++;
            else
                break;
        }

        // check if there is some fresh oranges in the matrix, if yes return -1
        // otherwise return time
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1)
                    return -1;
            }
        }

        return time;
    }

    public static void main(String[] args) {
        // Example 1
        int mat1[][] = new int[][]{
                {0, 1, 1},
                {2, 1, 2},
                {1, 0, 1}
        };
        System.out.println(minTimeToRot(mat1));

        // Example 2
        int mat2[][] = new int[][] {
                {0, 1, 0},
                {2, 0, 2},
                {1, 1, 1},
                {1, 1, 1}
        };
        System.out.println(minTimeToRot(mat2));
    }

    // class representing a coordinate in the matrix
    static class Coordinate {
        int row;
        int col;

        public Coordinate(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}
2
-1

လိမ္မော်သီးအားလုံးပုပ်ပျက်ရန်လိုအပ်သောအနည်းဆုံးအချိန်ကိုရှာရန် C ++ ကုဒ်

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

// class representing a coordinate in the matrix
class Coordinate {
    public:
    int row;
    int col;
    
    Coordinate(int r, int c) {
        row = r;
        col = c;
    }
};

int minTimeToRot(vector<vector<int>> &matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    
    // create a queue to store coordinates
    queue<Coordinate> q;
    // initialize a variable time as 0
    int time = 0;
    
    // Add all the rotten oranges coordinates to the queue
    // these acts as the starting point of the BFS
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 2) {
                Coordinate coordinate(i, j);
                q.push(coordinate);
            }
        }
    }
    
    while (!q.empty()) {
        // initialise size as size of queue
        int size = q.size();
        bool isSomeFreshRotten = false;
        // boolean variable representing whether or not an orange
        // is rotten in this time unit
        for (int i = 0; i < size; i++) {
            // remove an element from the queue
            Coordinate curr = q.front();
            q.pop();
            
            // generate the coordinates of adjacent cells
            // if the generated coordinates are valid and there is a fresh orange
            // add the generated coordinates to the queue and mark that orange as rotten
            
            // left adjacent
            int leftRow = curr.row - 1;
            int leftCol = curr.col;
            if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
                if (matrix[leftRow][leftCol] == 1) {
                    Coordinate coordinate(leftRow, leftCol);
                    q.push(coordinate);
                    matrix[leftRow][leftCol] = 2;
                    isSomeFreshRotten = true;
                }
            }

            // right adjacent
            int rightRow = curr.row + 1;
            int rightCol = curr.col;
            if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
                if (matrix[rightRow][rightCol] == 1) {
                    Coordinate coordinate(rightRow, rightCol);
                    q.push(coordinate);
                    matrix[rightRow][rightCol] = 2;
                    isSomeFreshRotten = true;
                }
            }

            // up adjacent
            int upRow = curr.row;
            int upCol = curr.col + 1;
            if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
                if (matrix[upRow][upCol] == 1) {
                    Coordinate coordinate(upRow, upCol);
                    q.push(coordinate);
                    matrix[upRow][upCol] = 2;
                    isSomeFreshRotten = true;
                }
            }

            // down adjacent
            int downRow = curr.row;
            int downCol = curr.col - 1;
            if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
                if (matrix[downRow][downCol] == 1) {
                    Coordinate coordinate(downRow, downCol);
                    q.push(coordinate);
                    matrix[downRow][downCol] = 2;
                    isSomeFreshRotten = true;
                }
            }
        }
        
        // if there is some oranges rotten in this time unit,
        // increment time else end the BFS here
        if (isSomeFreshRotten) {
            time++;
        } else {
            break;
        }
    }
    
    // check if there is some fresh oranges in the matrix, if yes return -1
    // otherwise return time
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1)
                return -1;
        }
    }
    
    return time;
}

int main() {
    // Example 1
    vector<vector<int>> mat1 {
        {0, 1, 1},
        {2, 1, 2},
        {1, 0, 1}
    };
    cout<<minTimeToRot(mat1)<<endl;
    
    // Example 2
    vector<vector<int>> mat2 {
        {0, 1, 0},
        {2, 0, 2},
        {1, 1, 1},
        {1, 1, 1}
    };
    cout<<minTimeToRot(mat2)<<endl;
    
    return 0;
}
2
-1

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (* * မီတာ)၊ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာ input matrix ထဲမှာရှိတဲ့ဆဲလ်တွေအားလုံးကိုဖြတ်သန်းသွားမယ့်ပထမ ဦး ဆုံးရှာဖွေမှုကိုသုံးထားလို့ပဲ။ ထို့ကြောင့်အချိန်ရှုပ်ထွေး polynomial ဖြစ်ပါတယ်။

အာကာသရှုပ်ထွေးမှု

အို (* * မီတာ)၊ BFS ကိုအသုံးပြုပြီးဒီအာကာသကိုယူ။ ဘာဖြစ်လို့လဲဆိုတော့ element တွေကိုသိုလှောင်ထားတဲ့ဒီစီမံကိန်းဟာ Queue ကိုသုံးတာပါပဲ။

ဘယ်မှာ n နှင့် m အသီးသီးပေးထားသော matrix ၏အတန်းများနှင့်ကော်လံဖြစ်ကြသည်။