მინიმალური დროა საჭირო ყველა ფორთოხლის გასანადგურებლად  



ხშირად ეკითხებიან Adobe Amazon Bloomberg microsoft
Array სიგანე პირველი ძებნა Matrix

პრობლემის განცხადება  

პრობლემა "მინიმალური დრო, რომელიც საჭიროა ყველა ფორთოხლის გასანადგურებლად" აცხადებს, რომ თქვენ გეძლევათ ა 2D მასივი, ყველა უჯრედს აქვს სამი, შესაძლო მნიშვნელობებიდან 0, 1 ან 2.
0 ნიშნავს ცარიელ უჯრედს.
1 ნიშნავს ახალ ფორთოხალს.
2 ნიშნავს დამპალ ნარინჯისფერს.
თუ დამპალი ფორთოხალი ახერხებს მის მიმდებარე ახალ ფორთოხალს 1 დროის ერთეულში, იპოვნეთ დრო ყველა ფორთოხლის გასანადგურებლად და თუ შეუძლებელია ყველა ფორთოხლის გამოწვა -1.

მაგალითები  

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

ალგორითმი ყველა ფორთოხლის გასანადგურებლად საჭირო მინიმალური დრო  

ყველა დამპალი ფორთოხალი საწყისი წერტილებია, ისინი ახდენენ მომიჯნავე ახალ ფორთოხალს 1 ერთეულ დროში. ყველა ფორთოხლის გასანადგურებლად საჭირო დრო რომ ვიპოვოთ, სიგანის პირველი ძებნა(BFS) ყველა დამპალი ფორთოხლის BFS საწყისი წერტილის აღებით.

  1. შექმნა მდგომ კოორდინატების, საჭირო უჯრედების კოორდინატების შესანახად, ანუ რიგში უნდა იყოს შენახული ფორმის მონაცემები (მწკრივი, სვეტი). ცვლადი დროის ინიცირება 0 – ით.
  2. გაიარეთ მოცემულ მატრიცაში და დაამატეთ რიგში ყველა დამპალი ფორთოხლის კოორდინატი.
  3. მიუხედავად იმისა, რომ რიგი ცარიელი არ არის, გაიმეორეთ 4 ნაბიჯი.
  4. ინიცირებადი ცვლადის ზომა, როგორც რიგის ზომა. აწარმოე მარყუჟი i- ს ტოლია 0-ის ზომა (არ შედის), და ყველა გამეორებაზე გამოდის რიგიდან ელემენტი. თუ მის მიმდებარე მხარეებზე არის ახალი ფორთოხალი (მარცხნივ, მარჯვნივ, ზემოდან და ქვემოდან), ამ ფორთოხლის კოორდინატები რიგისკენ მიიტანეთ და ეს ნარინჯისფერი აღინიშნეთ, როგორც დამპალი. თუ ახალი ფორთოხალი იყო, დრო გაზარდეთ 1 ერთზე.
  5. ახლა შეამოწმეთ, არის თუ არა ახალი ფორთოხალი მატრიცაში, თუ კი, ყველა ფორთოხალი არ შეიძლება დამპალი იყოს, ასე რომ დააბრუნეთ -1, სხვა შემთხვევაში დაბრუნების დრო.
იხილეთ ასევე
დიაგრამა და მისი წარმოდგენა

განმარტება

განვიხილოთ მაგალითი,
{
{0, 1, 1}
{2, 1, 2}
{1, 0, 1}
}

მინიმალური დროა საჭირო ყველა ფორთოხლის გასანადგურებლად

ყველა ფორთოხალი დამპალია დროს = 2.

კოდი  

ჯავის კოდი ყველა ფორთოხლის გასანადგურებლად საჭირო მინიმალური დრო

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

სირთულის ანალიზი  

დროის სირთულე

O (n * m), რადგან ჩვენ გამოვიყენეთ პირველი ძებნა სიგანე, რომელიც გადის ყველა უჯრედს შეყვანის მატრიცაში. ამრიგად, დროის სირთულე მრავალწევრია.

იხილეთ ასევე
ქვეჯგუფის ჯამი Leetcode

სივრცის სირთულე

O (n * m), BFS– ის გამოყენება ამ ადგილს იკავებს. რადგან იყენებს რიგს, რომელიც ინახავს ელემენტებს და, შესაბამისად, ამ სირთულეს.

სადაც n და m არის მოცემული მატრიცის სტრიქონები და სვეტები.