Bütün portağalların çürüməsi üçün tələb olunan minimum vaxt


Tez-tez soruşulur Çiy kərpic Amazon Bloomberg microsoft
Geyim Genişlik İlk Axtarış MatrisBaxılıb 30
LinkedInBuferRedditTumblr

Problem bəyanat

“Bütün portağalların çürüməsi üçün tələb olunan minimum vaxt” problemi sizə a 2D sıra, hər hüceyrədə 0, 1 və ya 2 mümkün üç dəyərdən biri vardır.
0 boş bir hüceyrə deməkdir.
1 təzə portağal deməkdir.
2 çürümüş portağal deməkdir.
Çürümüş portağal, ona bitişik olan təzə portağalın 1 dəfə vahidində çürüyə bilərsə, bütün portağalların çürüməsinə sərf olunan vaxtı tapın və bütün portağalların çürüməsi mümkün deyilsə -1.

Nümunələr

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

Bütün portağalları çürütmək üçün tələb olunan minimum vaxtı tapmaq üçün alqoritm

Bütün çürümüş portağallar başlanğıc nöqtələridir, bitişik təzə portağalları 1 vahiddə çürüyürlər. Bütün portağalları çürütmək üçün lazım olan ümumi vaxtı tapmaq üçün edə bilərik enli ilk axtarışBütün çürümüş portağalları BFS-nin başlanğıc nöqtəsi kimi qəbul edərək (BFS).

  1. Bir yaradın queue koordinatlar, tələb olunan hüceyrələrin koordinatlarını saxlamaq üçün, yəni növbə formanın məlumatlarını (satır, kol) saxlamalıdır. Dəyişən vaxtı 0 olaraq başlayın.
  2. Verilən matrisdən keçin və bütün çürümüş portağalların koordinatlarını növbəyə əlavə edin.
  3. Növbə boş olmasa da, 4-cü addımı təkrarlayın.
  4. Dəyişən ölçünü növbənin ölçüsü kimi başladın. I üçün 0-a bərabər bir döngə işlədin (daxil deyil) və hər təkrarlanmada növbədən bir element çıxartın. Bitişik tərəflərində (sol, sağ, yuxarı və alt) təzə narıncı varsa, həmin portağalın koordinatlarını növbəyə itələyin və həmin narıncı çürümüş kimi qeyd edin. Bir az təzə portağal olsaydı, vaxtı 1 vahid artırın.
  5. İndi matrisdə hələ də bir az təzə portağalın olub olmadığını yoxlayın, bəli, bütün portağallar çürüyə bilməz, buna görə -1 -ə qayıdın, əks halda geri qayıdır.

Izahat

Nümunəni nəzərdən keçirək,
{
{0, 1, 1}
{2, 1, 2}
{1, 0, 1}
}

Bütün portağalların çürüməsi üçün tələb olunan minimum vaxtPin

Bütün portağallar zamanında çürümüşdür = 2.

Kodu

Java kodunu tapmaq üçün bütün portağalları çürütmək üçün minimum vaxt lazımdır

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

Bütün portağalların çürüməsi üçün tələb olunan minimum vaxtı tapmaq üçün C ++ kodu

#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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n * m), çünki giriş matrisindəki bütün hüceyrələri keçəcək İlk Axtarışdan genişlik istifadə etdik. Beləliklə zamanın mürəkkəbliyi polinomdur.

Kosmik Mürəkkəblik

O (n * m), BFS istifadə edərək bu yeri tutur. Çünki elementləri saxlayan növbədən və beləliklə bu mürəkkəblikdən istifadə edir.

N və m müvafiq olaraq verilən matrisin sətirləri və sütunlarıdır.

LinkedInBuferRedditTumblr
Translate »