সমস্ত কমলা পচতে ন্যূনতম সময় প্রয়োজন



প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক ব্লুমবার্গ মাইক্রোসফট
বিন্যাস প্রস্থ প্রথম অনুসন্ধান জরায়ু

সমস্যা বিবৃতি

"সমস্ত কমলা পচতে ন্যূনতম সময় প্রয়োজন" সমস্যাটি বলে যে আপনাকে একটি দেওয়া হয়েছে 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

সমস্ত কমলা নষ্ট করার জন্য ন্যূনতম সময় প্রয়োজন find

সমস্ত পচা কমলা প্রারম্ভিক পয়েন্ট, তারা সংলগ্ন তাজা কমলাগুলিকে সময় 1 ইউনিটে পচায়। সমস্ত কমলা পচে যাওয়ার জন্য মোট সময় প্রয়োজন তা আমরা করতে পারি প্রথমতম অনুসন্ধান(বিএফএস) সমস্ত পচা কমলা বিএফএসের শুরুর দিক হিসাবে ধরে নিয়ে।

  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

সমস্ত কমলা পচতে ন্যূনতম সময় প্রয়োজন সন্ধান করতে সি ++ কোড

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন * মি), কারণ আমরা প্রস্থের প্রথম অনুসন্ধান ব্যবহার করেছি যা ইনপুট ম্যাট্রিক্সের সমস্ত কক্ষকে অতিক্রম করবে। সুতরাং সময় জটিলতা বহুপদী।

স্পেস জটিলতা ity

ও (এন * মি), বিএফএস ব্যবহার করে এই স্থান নেয়। কারণ সারি ব্যবহার করে যা উপাদানগুলি সংরক্ষণ করে এবং এইভাবে এই জটিলতা।

যেখানে n এবং m যথাক্রমে প্রদত্ত ম্যাট্রিক্সের সারি এবং কলাম।