Բոլոր նարինջները փտելու համար անհրաժեշտ նվազագույն ժամանակը



Հաճախակի հարցնում են Adobe Amazon Bloomberg Microsoft
Դասավորություն Լայնության առաջին որոնում Matrix

Խնդիրի հայտարարություն

«Բոլոր նարինջները փչացնելու համար անհրաժեշտ նվազագույն ժամանակը» խնդիրը նշում է, որ ձեզ տրվում է ա 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 միավորի ընթացքում: Բոլոր նարինջները փչացնելու համար պահանջվող ընդհանուր ժամանակը գտնելու համար մենք կարող ենք անել ա լայնության առաջին որոնումը(BFS) ՝ բոլոր փտած նարինջները որպես BFS- ի ելակետ ընդունելով:

  1. Ստեղծել հերթ կոորդինատների համար, անհրաժեշտ բջիջների կոորդինատները պահելու համար, այսինքն, հերթում պետք է պահվեն ձևի տվյալները (տող, սյուն): Նախաձևակերպեք փոփոխական ժամանակը որպես 0:
  2. Տրված մատրիցով անցնելը և հերթին ավելացնել բոլոր փտած նարինջների կոորդինատները:
  3. Չնայած հերթը դատարկ չէ, կրկնում է 4-րդ քայլը:
  4. Նախաձեռնեք փոփոխականի չափը որպես հերթի չափը: Run մի օղակ i- ի համար հավասար է 0-ի չափի (ներառված չէ), և յուրաքանչյուր կրկնության ժամանակ հերթից դուրս է գալիս մի տարր: Եթե ​​դրա հարակից կողմերում կա թարմ նարնջագույն (ձախ, աջ, վերև և ներքև), ապա այդ նարնջի կոորդինատները մղեք հերթ և նշեք այդ նարինջը որպես փտած: Եթե ​​կան մի քանի թարմ նարինջ, ապա ժամանակն ավելացրեք 1 միավորով:
  5. Այժմ ստուգեք, արդյոք մատրիցայում դեռ թարմ նարնջագույն կա, եթե այո, բոլոր նարինջները չեն կարող փտած լինել, այնպես որ վերադարձեք -1, այլապես վերադարձի ժամանակը:

բացատրություն

Հաշվի առեք օրինակը,
{
{0, 1, 1}
{2, 1, 2}
{1, 0, 1}
}

Բոլոր նարինջները փտելու համար անհրաժեշտ նվազագույն ժամանակը

Բոլոր նարինջները փտած են ժամանակին = 2:

Կոդ

Java կոդ ՝ բոլոր նարինջները փչացնելու համար պահանջվող նվազագույն ժամանակը

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 ++ կոդ ՝ բոլոր նարինջները փչացնելու համար պահանջվող նվազագույն ժամանակը

#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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n * m), քանի որ մենք օգտագործել ենք լայնության Առաջին որոնումը, որը անցնելու է մուտքային մատրիցի բոլոր բջիջները: Այսպիսով, ժամանակի բարդությունը բազմանդամ է:

Տիեզերական բարդություն

O (n * m), BFS- ի օգտագործումը տանում է այս տարածքը: Քանի որ օգտագործում է հերթերը, որոնք պահում են տարրերը և, այդպիսով, այս բարդությունը:

Որտեղ n և m համապատասխանաբար տրված մատրիցի տողերն ու սյուններն են: