සියලුම දොඩම් කුණුවීමට අවශ්‍ය අවම කාලය



නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් බ්ලූම්බර්ග් මයික්රොසොෆ්ට්
අරා පළල පළමු සෙවීම නියමයන්

ගැටළු ප්රකාශය

“සියලු දොඩම් කුණුවීමට අවශ්‍ය අවම කාලය” යන ගැටලුවෙහි දැක්වෙන්නේ ඔබට ලබා දී ඇති බවයි 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 සිට ප්‍රමාණයට සමාන වන ලූපයක් ධාවනය කරන්න (ඇතුළත් කර නැත), සහ සෑම නැවතීමේ දීම පෝලිමේ සිට මූලද්‍රව්‍යයක් පිටතට පැමිණේ. එහි යාබද පැතිවල (වමේ, දකුණ, ඉහළ සහ පහළ) නැවුම් තැඹිලි පාට තිබේ නම්, එම තැඹිලි වල ඛණ්ඩාංක පෝලිම්වලට තල්ලු කර එම තැඹිලි දිරාපත් වූ ලෙස සලකුණු කරන්න. නැවුම් දොඩම් කිහිපයක් තිබුනේ නම් කාලය ඒකක 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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (n * m), ආදාන අනුකෘතියේ සියලුම සෛල හරහා ගමන් කරන පළල පළමු සෙවුම අප භාවිතා කර ඇති බැවිනි. මේ අනුව කාල සංකීර්ණතාව බහුපද වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (n * m), BFS භාවිතා කිරීම මෙම අවකාශය ගනී. මන්ද යත් මූලද්‍රව්‍ය ගබඩා කරන පෝලිම් භාවිතා කරන අතර එමඟින් මෙම සංකීර්ණතාවයි.

මෙහි n සහ m යනු ලබා දී ඇති අනුකෘතියේ පේළි සහ තීරු වේ.