എല്ലാ ഓറഞ്ചും ചീഞ്ഞഴയാൻ കുറഞ്ഞ സമയം ആവശ്യമാണ്  



പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ബ്ലൂംബർഗ് മൈക്രോസോഫ്റ്റ്
അറേ വീതിയുടെ ആദ്യ തിരയൽ മാട്രിക്സ്

പ്രശ്നം പ്രസ്താവന  

“എല്ലാ ഓറഞ്ചും ചീഞ്ഞഴുകാൻ ആവശ്യമായ കുറഞ്ഞ സമയം” എന്ന പ്രശ്നം നിങ്ങൾക്ക് നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു 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 യൂണിറ്റ് സമയം കൊണ്ട് ചീഞ്ഞഴുകുന്നു. എല്ലാ ഓറഞ്ചുകളും ചീഞ്ഞഴുകാൻ ആവശ്യമായ ആകെ സമയം കണ്ടെത്താൻ നമുക്ക് a വീതി-ആദ്യ തിരയൽ(BFS) എല്ലാ ചീഞ്ഞ ഓറഞ്ചുകളും BFS ന്റെ ആരംഭ പോയിന്റായി കണക്കാക്കി.

  1. സൃഷ്ടിക്കുക വരി ആവശ്യമുള്ള സെല്ലുകളുടെ കോർഡിനേറ്റുകൾ സംഭരിക്കുന്നതിന്, അതായത്, ക്യൂവിന്റെ ഫോമിന്റെ ഡാറ്റ (വരി, കോൾ) സംഭരിക്കണം. ഒരു വേരിയബിൾ സമയം 0 ആയി സമാരംഭിക്കുക.
  2. തന്നിരിക്കുന്ന മാട്രിക്സിൽ സഞ്ചരിച്ച് എല്ലാ ചീഞ്ഞ ഓറഞ്ചുകളുടെയും കോർഡിനേറ്റുകൾ ക്യൂവിലേക്ക് ചേർക്കുക.
  3. ക്യൂ ശൂന്യമല്ലെങ്കിലും ഘട്ടം 4 ആവർത്തിക്കുക.
  4. ക്യൂവിന്റെ വലുപ്പമായി വേരിയബിൾ വലുപ്പം സമാരംഭിക്കുക. ഞാൻ 0 മുതൽ വലുപ്പം വരെ തുല്യമായി ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക (ഉൾപ്പെടുത്തിയിട്ടില്ല), ഓരോ ആവർത്തനത്തിലും ക്യൂവിൽ നിന്ന് ഒരു ഘടകം പോപ്പ് out ട്ട് ചെയ്യുക. അടുത്തുള്ള വശങ്ങളിൽ (ഇടത്, വലത്, മുകളിൽ, താഴെ) ഒരു പുതിയ ഓറഞ്ച് ഉണ്ടെങ്കിൽ, ആ ഓറഞ്ചിന്റെ കോർഡിനേറ്റുകളെ ക്യൂവിലേക്ക് നീക്കി ആ ഓറഞ്ച് ചീഞ്ഞതായി അടയാളപ്പെടുത്തുക. കുറച്ച് പുതിയ ഓറഞ്ച് ഉണ്ടെങ്കിൽ സമയം 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

സങ്കീർണ്ണത വിശകലനം  

സമയ സങ്കീർണ്ണത

O (n * m), കാരണം ഇൻ‌പുട്ട് മാട്രിക്സിലെ എല്ലാ സെല്ലുകളിലേക്കും സഞ്ചരിക്കുന്ന വീതിയുള്ള ആദ്യ തിരയൽ‌ ഞങ്ങൾ‌ ഉപയോഗിച്ചു. അങ്ങനെ സമയ സങ്കീർണ്ണത പോളിനോമിയലാണ്.

ഇതും കാണുക
സബ്സെറ്റ് സം ലീറ്റ്കോഡ്

ബഹിരാകാശ സങ്കീർണ്ണത

O (n * m), BFS ഉപയോഗിക്കുന്നത് ഈ ഇടം എടുക്കുന്നു. കാരണം ഘടകങ്ങൾ സംഭരിക്കുന്ന ക്യൂ ഉപയോഗിക്കുകയും ഈ സങ്കീർണ്ണത ഉപയോഗിക്കുകയും ചെയ്യുന്നു.

ഇവിടെ n ഉം m ഉം യഥാക്രമം തന്നിരിക്കുന്ന മാട്രിക്സിന്റെ വരികളും നിരകളുമാണ്.