უახლოესი უჯრედის მანძილი, რომელსაც აქვს 1 ორობით მატრიცაში


Რთული ტური Hard
ხშირად ეკითხებიან Accenture Amazon Honeywell HSBC Hulu Twitter
Array სიგანე პირველი ძებნა Graph Matrix Queue

პრობლემის განცხადება

პრობლემა "უახლოესი უჯრედის მანძილი, რომელსაც აქვს 1 ორობით მატრიცაში" აცხადებს, რომ გეძლევათ ორობითი matrix(შეიცავს მხოლოდ 0-ს და 1-ს) მინიმუმ ერთით. 1. იპოვნეთ უახლოესი უჯრედის მანძილი, რომელსაც აქვს 1 ორობითი მატრიცაში მატრიცის ყველა ელემენტისთვის, აქ მანძილი ორ უჯრედს (x1, y1) და (x2, y2) ) არის | x2 - x1 | + | y2 - y1 |.

მაგალითები

{
{0, 1, 0}
{0, 0, 0}
{1, 0, 0}
}
{
{1, 0, 1}
{1, 1, 2}
{0, 1, 2}
}

განმარტება: ჩვენ შეგვიძლია დავინახოთ, რომ 1 უჯრედს აქვს 0 მატრიქსში და უჯრედები 1 უჯრედისგან 1 დაშორებით. ამ უჯრედებს გამომავალი აქვთ 1 და ანალოგიურად, სხვა უჯრედებისათვისაც გამოითვლება მანძილი.

{
{0, 0, 0}
{0, 0, 0}
{1, 0, 1}
}
{
{2, 3, 2}
{1, 2, 1}
{0, 1, 0}
}

გულუბრყვილო მიდგომა

მატრიცის ყველა ელემენტისთვის გადაკვეთა მთელი matrix და იპოვნეთ უჯრედი მინიმალური მანძილით, რომელსაც აქვს მატრიცაში 1.

  1. შექმენით ზომის მასივები, ისევე როგორც მასივის მატრიცა. აწარმოეთ ორი ჩასმული მარყუჟი მატრიცის ყველა ელემენტის გასავლელად.
  2. მატრიცის თითოეული ელემენტისთვის აწარმოეთ კიდევ ორი ​​წყობილი მარყუჟი მატრიცის თითოეული ელემენტის გასავლელად, მოდით ეს შეგვიძლია როგორც მიმდინარე ელემენტს. ყველა ამჟამინდელი ელემენტისთვის, რომლებიც არის 1, იპოვნეთ მინიმალური მანძილის ელემენტი და შეინახეთ ეს მანძილი ans მასივში.
  3. დაბეჭდე ans მასივი.

სირთულის ანალიზი

დროის სირთულე = ო (ნ2 * მ2)
სივრცის სირთულე = O (n * m)
სადაც n და m არის მოცემული მატრიცის სტრიქონები და სვეტები.

მას შემდეგ, რაც ჩვენ ვათვალიერებთ მატრიქსში თითოეული უჯრედის მთელ მატრიქსს. ეს ალგორითმს აწარმოებს უფრო მაღალ სირთულეში. სივრცის სირთულე მხოლოდ გამომავალი შენახვის გამო, მაგრამ თავად ალგორითმი მოითხოვს მუდმივ ადგილს. თუ ჩვენ უბრალოდ გამოვაქვეყნებდით შედეგს, მაშინ ამ სივრცის სირთულეც შემცირდებოდა.

კოდი

ჯავის კოდი, რომ იპოვოთ უახლოესი უჯრედის მანძილი, რომელსაც აქვს 1 ორობით მატრიცაში

class DistanceOfNearestCellHaving1InABinaryMatrix {
    private static void minimumDistance(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        int[][] ans = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int minDist = Integer.MAX_VALUE;
                for (int x = 0; x < n; x++) {
                    for (int y = 0; y < m; y++) {
                        if (matrix[x][y] == 1) {
                            int dist = Math.abs(x - i) + Math.abs(y - j);
                            minDist = Math.min(minDist, dist);
                        }
                    }
                }
                ans[i][j] = minDist;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int matrix1[][] = new int[][]{
                {0, 1, 0},
                {0, 0, 0},
                {1, 0, 0}
        };
        minimumDistance(matrix1);

        int matrix2[][] = new int[][]{
                {0, 0, 0},
                {0, 0, 0},
                {1, 0, 1}
        };
        minimumDistance(matrix2);
    }
}
1 0 1 
1 1 2 
0 1 2 

2 3 2 
1 2 1 
0 1 0

C ++ კოდი, რომ იპოვოთ უახლოესი უჯრედის მანძილი, რომელსაც აქვს 1 ორობით მატრიცაში

#include<bits/stdc++.h> 
using namespace std; 

void minimumDistance(vector<vector<int>> &matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    
    int ans[n][m];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int minDist = INT_MAX;
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < m; y++) {
                    if (matrix[x][y] == 1) {
                        int dist = abs(x - i) + abs(y - j);
                        minDist = std::min(minDist, dist);
                    }
                }
            }
            ans[i][j] = minDist;
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
              cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

int main() {
    // Example 1
    vector<vector<int>> matrix1 = {
            {0, 1, 0},
            {0, 0, 0},
            {1, 0, 0}
    };
    minimumDistance(matrix1);

    // Example 2
    vector<vector<int>> matrix2 = {
            {0, 0, 0},
            {0, 0, 0},
            {1, 0, 1}
    };
    minimumDistance(matrix2);
    
    return 0;
}
1 0 1 
1 1 2 
0 1 2 

2 3 2 
1 2 1 
0 1 0

ოპტიმალური მიდგომა

უკეთესი მიდგომაა BFS– ის გაკეთება დაწყებული მოცემული მატრიცის ყველა 1 – დან. ყველა 1-ის მანძილი ნულოვანია და ყველა მიმდებარედ მინიმალური მანძილი ამაზე ერთით მეტია.

  1. შექმნა მდგომ კოორდინატები, რომელიც გამოიყენება ელემენტის (მწკრივი, სვეტი) შესანახად. შექმნა მასივი ზომის იგივეა, რაც მასივი matrix.
  2. გაიარეთ მატრიცის ყველა ელემენტი და დააჭირეთ რიგში ელემენტების კოორდინატებს.
  3. ინიციალეთ ცვლადი minDistance როგორც 0. სანამ რიგი არ არის ცარიელი, გაიმეორეთ მე -4 და მე -5 ნაბიჯები.
  4. ინიცირებადი ცვლადის ზომა, როგორც რიგის ზომა. აწარმოე მარყუჟი i- ს ტოლია 0-ის ზომა (არ შედის). ყველა გამეორებაზე რიგიდან გამოდის ელემენტი. Ans [row] [col] მიუთითეთ minDistance- ით და მიუთითეთ ამ ელემენტის ყველა მოქმედი მიმდევარი, რომლებიც მატრიცის მასივშია 0 და დააყენეთ 1, როგორც მატრიცის მასივში.
  5. გაზრდა minD მანძილი.
  6. დაბეჭდე ans მასივი.

სირთულე ანლაზი

დროის სირთულე = O (n * m)
სივრცის სირთულე = O (n * m)
სადაც n და m არის მოცემული მატრიცის სტრიქონები და სვეტები.

ალგორითმი ძალიან ჰგავს BFS- ს გრაფიკისთვის და ამრიგად მხოლოდ O (N * M) დროა აღებული.

განმარტება

განვიხილოთ მაგალითი,
{
{0, 1, 0}
{0, 0, 0}
{1, 0, 0}
}

უახლოესი უჯრედის მანძილი, რომელსაც აქვს 1 ორობით მატრიცაში

კოდი

ჯავის კოდი, რომ იპოვოთ უახლოესი უჯრედის მანძილი, რომელსაც აქვს 1 ორობით მატრიცაში

import java.util.LinkedList;
import java.util.Queue;
class Optimal {
    private static void minimumDistance(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        // create an array ans of size same as matrix array
        int ans[][] = new int[n][m];

        // create a queue of coordinates
        // push all the elements that are equals to 1 in the matrix array to the queue
        Queue<Coordinate> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 1) {
                    queue.add(new Coordinate(i, j));
                }
            }
        }

        // initialize minDistance as 0
        int minDistance = 0;

        while (!queue.isEmpty()) {
            // initialize size as size of queue
            int size = queue.size();

            // Run a loop size times
            for (int i = 0; i < size; i++) {
                // remove an element from queue
                Coordinate curr = queue.poll();

                // ans to this coordinate is minDistance
                ans[curr.row][curr.col] = minDistance;

                // enqueue all the valid adjacent cells of curr that are equals to
                // 0 in the matrix array and set them as 1

                // left adjacent
                int leftRow = curr.row - 1;
                int leftCol = curr.col;
                if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
                    if (matrix[leftRow][leftCol] == 0) {
                        queue.add(new Coordinate(leftRow, leftCol));
                        matrix[leftRow][leftCol] = 1;
                    }
                }

                // right adjacent
                int rightRow = curr.row + 1;
                int rightCol = curr.col;
                if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
                    if (matrix[rightRow][rightCol] == 0) {
                        queue.add(new Coordinate(rightRow, rightCol));
                        matrix[rightRow][rightCol] = 1;
                    }
                }

                // up adjacent
                int upRow = curr.row;
                int upCol = curr.col + 1;
                if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
                    if (matrix[upRow][upCol] == 0) {
                        queue.add(new Coordinate(upRow, upCol));
                        matrix[upRow][upCol] = 1;
                    }
                }

                // down adjacent
                int downRow = curr.row;
                int downCol = curr.col - 1;
                if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
                    if (matrix[downRow][downCol] == 0) {
                        queue.add(new Coordinate(downRow, downCol));
                        matrix[downRow][downCol] = 1;
                    }
                }
            }

            // increment minimum distance
            minDistance++;
        }

        // print the elements of the ans array
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        int matrix1[][] = new int[][]{
                {0, 1, 0},
                {0, 0, 0},
                {1, 0, 0}
        };
        minimumDistance(matrix1);

        // Example 2
        int matrix2[][] = new int[][]{
                {0, 0, 0},
                {0, 0, 0},
                {1, 0, 1}
        };
        minimumDistance(matrix2);
    }

    // class representing coordinates of a cell in matrix
    static class Coordinate {
        int row;
        int col;

        public Coordinate(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}
1 0 1 
1 1 2 
0 1 2 

2 3 2 
1 2 1 
0 1 0

C ++ კოდი, რომ იპოვოთ უახლოესი უჯრედის მანძილი, რომელსაც აქვს 1 ორობით მატრიცაში

#include<bits/stdc++.h> 
using namespace std; 

// class representing coordinates of a cell in matrix
class Coordinate {
    public:
    int row;
    int col;
    
    Coordinate(int r, int c) {
        row = r;
        col = c;
    }
};

void minimumDistance(vector<vector<int>> &matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    
    // create an array ans of size same as matrix array
    int ans[n][m];
    
    // create a queue of coordinates
    // push all the elements that are equals to 1 in the matrix array to the queue
    queue<Coordinate> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1) {
                Coordinate coordinate(i, j);
                q.push(coordinate);
            }
        }
    }
    
    // initialize minDistance as 0
    int minDistance = 0;
    
    while (!q.empty()) {
        // initialize size as size of queue
        int size = q.size();
        
        // Run a loop size times
        for (int i = 0; i < size; i++) {
            // remove an element from queue
            Coordinate curr = q.front();
            q.pop();
            
            // ans to this coordinate is minDistance
            ans[curr.row][curr.col] = minDistance;
            
            // enqueue all the valid adjacent cells of curr that are equals to
            // 0 in the matrix array and set them as 1
            
            // left adjacent
            int leftRow = curr.row - 1;
            int leftCol = curr.col;
            if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
                if (matrix[leftRow][leftCol] == 0) {
                    Coordinate cLeft(leftRow, leftCol);
                    q.push(cLeft);
                    matrix[leftRow][leftCol] = 1;
                }
            }
            
            // right adjacent
            int rightRow = curr.row + 1;
            int rightCol = curr.col;
            if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
                if (matrix[rightRow][rightCol] == 0) {
                    Coordinate cRight(rightRow, rightCol);
                    q.push(cRight);
                    matrix[rightRow][rightCol] = 1;
                }
            }
            
            // up adjacent
            int upRow = curr.row;
            int upCol = curr.col + 1;
            if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
                if (matrix[upRow][upCol] == 0) {
                    Coordinate cUp(upRow, upCol);
                    q.push(cUp);
                    matrix[upRow][upCol] = 1;
                }
            }
            
            // down adjacent
            int downRow = curr.row;
            int downCol = curr.col - 1;
            if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
                if (matrix[downRow][downCol] == 0) {
                    Coordinate cDown(downRow, downCol);
                    q.push(cDown);
                    matrix[downRow][downCol] = 1;
                }
            }
        }
        
        // increment minimum distance
        minDistance++;
    }
    
    // print the elements of the ans array
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

int main() {
    // Example 1
    vector<vector<int>> matrix1 = {
            {0, 1, 0},
            {0, 0, 0},
            {1, 0, 0}
    };
    minimumDistance(matrix1);

    // Example 2
    vector<vector<int>> matrix2 = {
            {0, 0, 0},
            {0, 0, 0},
            {1, 0, 1}
    };
    minimumDistance(matrix2);
    
    return 0;
}
1 0 1 
1 1 2 
0 1 2 

2 3 2 
1 2 1 
0 1 0