گهٽ ۾ گهٽ وقت جي ضرورت آهي سڀ نارنگي ڀ rotڻ لاءِ



بار بار پڇڻ ۾ ايڊوب Amazon Bloomberg Microsoft جي
ڪيريو ماني لاءِ پهرين ڳولا قائم ٿينديون

مسئلي جو بيان

مسئلو ”گهٽ ۾ گهٽ وقت گهرجي سڀني نارنگين جو گل ڪرڻ“ لاءِ اهو ٻڌائي ٿو ته توهان کي هڪ ڏني وئي آهي 2D صف، هر خاني ۾ ٽن ممڪن قدرن مان هڪ آهي 0 ، 1 يا 2.
0 مطلب آھي خالي خانو.
1 جو مطلب ھڪڙو نارنگي آھي.
2 مطلب ھڪڙو ٻرندڙ نارنگي.
جيڪڏھن ڪو سڪو نارنج 1 وقت يونٽ ۾ ان سان ڀريل تازو نارنگي کي canري سگھي ٿو ، سڀني نارنگي کي rotلڻ لاءِ کڻي ويو وقت ڳوليو ۽ جيڪڏھن سڀني نارنگي کي پرنٽ ڪرڻ ممڪن نه -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 يونٽ ۾ ويجھي تازي نارنگين کي rotٽي ڇڏينديون آھن. سڀ نارنگي روءِ ڪرڻ لاءِ گهربل وقت گهرڻ لاءِ اسين ڪري سگھون ٿا چوٿون- پهرين ڳولا(بي ايف ايس) theڻ سڀني سڙيل سنتري کي بي ايف ايس جو شروعاتي مقام سمجهندو.

  1. هڪ ٺاهيو پنگتي حيثيت رکي ٿو تنظيمن کي ، گهربل خانن جي همراه کي اسٽور ڪرڻ ، يعني ، قطار کي فارم جي ڊيٽا کي اسٽور ڪرڻ گهرجي (قطار ، ڪلي). شروعاتي طور تي 0 طور تي متغير وقت ڪريو.
  2. ڏنل ميٽرڪس ۾ سفر ڪريو ۽ قطار ۾ سڀني بگڙيل نارنگي جي همراهڪن کي شامل ڪريو.
  3. جڏهن ته قطار خالي ناهي دير واري قدم 4.
  4. قطار جي قد جي حساب سان ھڪڙي متغير شڪل کي شروع ڪريو. مون لاءِ لوپ هلايو مون کي 0 جي سائيز برابر آهي (شامل نه آهي) ، ۽ هر هر وهڪ تي هڪ قطار کي قطار مان ٻاهر ڏيکاري ٿي. جيڪڏهن ان جي ڀرپاسي وارن طرف orangeڻ تازو نارنج آهي (کاٻي ، سا rightي ، مٿان ۽ هيٺيون) ، انهي نارنگي جي همراه کي قطار ڏانهن ڌڪيو ۽ نشانين کي خراب وانگر نشان هڻو جيڪڏهن ڪي تازا ڪارا ميوا هوندا ته پوءِ 1 يونٽ پاران وقت کي وڌايو.
  5. ھاڻي چيڪ ڪريو ته ڇا اتي ڪجھ تازو نارنگي اڃا تائين ميٽرڪس ۾ موجود آھي ، جيڪڏھن ھا ، سڀ نارنگيون ڏا beي خراب ٿي سگھن ٿيون تنھنڪري موٽي -1 ، ٻي صورت ۾ وقت واپس.

وضاحت

مثال تي غور ڪريو.
{
{0، 1، 1}
{2، 1، 2}
{1، 0، 1}
}

گهٽ ۾ گهٽ وقت جي ضرورت آهي سڀ نارنگي ڀ rotڻ لاءِ

سڀ نارنگي وقت تي areري چڪا آهن = 2.

ڪوڊ

جاوا ڪوڊ ڳولڻ لاءِ گھٽ ۾ گھٽ وقت لازمي طور تي سڀني نارنگي کي toُري ويو

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

سي ++ ڪوڊ ڳولڻ لاءِ گھٽ ۾ گھٽ وقت لازمي طور تي سڀني نارنگي کي جھليو وڃي

#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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (ن * م) ، ڇاڪاڻ ته اسان چوٿائي فرسٽ سرچ استعمال ڪيو آهي جيڪو انپٽ ميٽرڪس جي سڀني خاني مان لنگهائيندو. ان ڪري وقت جي پيچيدگي پولينومل آهي.

خلائي پيچيدگي

اي (ن * م) ، BFS استعمال ڪندي ھن جڳھ وٺندي آھي. ڇاڪاڻ ته انهي قطار کي استعمال ڪري ٿي جيڪا عناصر کي محفوظ ڪري ٿي ۽ اهڙي طرح اها پيچيدگي.

جتي n ۽ m ترتيب ڏنل ڏنل ميٽرڪس جي قطار ۽ ڪالمن آهن.