Экинчи матрицада 1 жакын турган уячанын аралыгы


Кыйынчылык деңгээли катуу
Көп суралган Accenture Amazon ЭлЭлПи HSBC Hulu Twitter
согуштук тизме Биринчи издөө график Matrix кезек

Маселени билдирүү

"Бинардык матрицада 1 жакын турган уячанын аралыгы" маселеси сизге бинардык деп берилгенин билдирет Булакта(жок дегенде 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}
}

Naive Appocach

Матрицанын ар бир элементи үчүн бүтүн өтүңүз Булакта жана матрицада 1 эң аз аралыкта жайгашкан уячаны табуу.

  1. Массив матрицасы сыяктуу көлөмдөгү массивди түзүңүз. Матрицанын бардык элементтерин айланып өтүү үчүн, эки уялуу циклди чуркаңыз.
  2. Матрицанын ар бир элементин өткөрүү үчүн, матрицанын ар бир элементин өтүш үчүн дагы эки уялуу циклди чуркап өтүңүз, учурдагы элемент катары. Учурдагы бардык 1 элементтер үчүн, аралыктын минималдуу элементин таап, ал аралыкты ans массивинде сактаңыз.
  3. Ans массивин басып чыгаруу.

Комплекстик анализ

Убакыт татаалдыгы = O (n2 * м2)
Космостун татаалдыгы = O (n * m)
мында n жана m - тиешелүүлүгүнө жараша берилген матрицанын катарлары жана тилкелери.

Матрицанын ар бир уячасы үчүн бүт матрицаны аралап жаткандыктан. Бул алгоритмди жогорку убакыт татаалдыгында иштетет. Космостун татаалдыгы - бул чыгарылган нерсенин сакталышы, бирок алгоритмдин өзү туруктуу орун талап кылат. Эгерде биз жөн гана чыгарууну басып чыгармак болсок, анда бул мейкиндиктин татаалдыгы дагы азаймак.

коду

Бинардык матрицада 1ге ээ болгон жакынкы уячанын Аралыгын табуу үчүн Java коду

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

Оптималдуу ыкма

Берилген матрицанын бардык 1синен баштап BFS жасоо жакшы ыкма. Бардык 1лердин аралыгы нөлгө барабар, ал эми чектеш баардыгы үчүн минималдуу аралык мындан бир эсе ашат.

  1. түзүү кезек элементинин (сап, тилке) сакталуусу үчүн колдонулган Координаттар. Түзүү согуштук тизме массив менен бирдей көлөмдөгү анс Булакта.
  2. Матрицанын бардык элементтерин аралап өтүп, 1 болгон элементтердин координаттарын кезекке тургузуңуз.
  3. MinDistance өзгөрмөсүн 0 деп инициализациялаңыз, ал эми кезек бош эмес 4 жана 5-кадамдарды кайталаңыз.
  4. Кезектин көлөмү катары өзгөрүлмө өлчөмдү баштаңыз. I үчүн 0 циклине барабар цикл иштетүү (киргизилген эмес). Ар бир кайталоодо кезектеги элемент чыгат. Ans [row] [col] маанисин minDistance кылып коюп, ушул элементтин матрицалык массивде 0 болгон бардык жарактуу чектештерин тизмелеп, аларды матрицалык массивде 1 деп кой.
  5. Аралыгы мин.
  6. Ans массивин басып чыгаруу.

Комплекстүүлүк Anlaysis

Убакыт татаалдыгы = O (n * m)
Космостун татаалдыгы = O (n * m)
мында n жана m - тиешелүүлүгүнө жараша берилген матрицанын катарлары жана тилкелери.

Алгоритм графиктер үчүн BFSге абдан окшош, ошондуктан O (N * M) убактысы гана алынган.

түшүндүрүү

Мисалды карап көрөлү,
{
{0, 1, 0}
{0, 0, 0}
{1, 0, 0}
}

Экинчи матрицада 1 жакын турган уячанын аралыгы

коду

Бинардык матрицада 1ге ээ болгон жакынкы уячанын Аралыгын табуу үчүн Java коду

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