حداقل زمان لازم برای پوسیدگی تمام پرتقال ها



اغلب در خشت آمازون بلومبرگ مایکروسافت
صف عرض اول جستجو ماتریس

بیان مسأله

مشکل "حداقل زمان لازم برای پوسیدگی تمام پرتقال ها" بیانگر این است که به شما a آرایه 2 بعدی، هر سلول یکی از سه مقدار ممکن 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 ++ Code برای پیدا کردن حداقل زمان لازم برای پوسیدگی تمام پرتقال ها

#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) ، زیرا ما از جستجوی اول استفاده کرده ایم که تمام سلول های ماتریس ورودی را پیمایش می کند. بنابراین پیچیدگی زمان چند جمله ای است.

پیچیدگی فضا

O (n * m) ، استفاده از BFS این فضا را می گیرد. زیرا از صف استفاده می کند که عناصر را ذخیره می کند و بنابراین از این پیچیدگی استفاده می کند.

جایی که n و m به ترتیب ردیف ها و ستون های ماتریس داده شده هستند.