Хоёртын матрицад 1 байх хамгийн ойрын нүдний зай


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Accenture Амазоны Honeywell HSBC Hulu Twitter
Array Өргөн уудам хайлт График матриц дараалал

Асуудлын мэдэгдэл

“Хоёртын матрицад 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}
}

Гэнэн хандлага

Матрицын бүх элементийн хувьд бүхэлд нь тайрч ав Матриц матрицад 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

Хоёртын матрицад 1 байх хамгийн ойрын нүдний зайг олох C ++ код

#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. Бүтээх дараалал of koordinat, элементийн (мөр, багана) хадгалахад ашигладаг. Үүсгэх массив массивтай ижил хэмжээтэй ans Матриц.
  2. Матрицын бүх элементүүдийг дайрч, 1-т багтсан элементийн координатыг дараалалд оруулна.
  3. MinDistance гэсэн хувьсагчийг 0 гэж эхлүүлнэ. Дараалал хоосон биш бол 4 ба 5-р алхамыг давтана.
  4. Хувьсах хэмжээг дарааллын хэмжээгээр эхлүүлнэ. I-ийн хэмжээтэй тэнцүү гогцоо ажиллуулна уу (оруулаагүй болно). Давталт бүрт дарааллын элемент гарч ирнэ. Ans [row] [col] -г minDistance гэж тохируулаад, энэ элементийн матрицын массив дотор 0 байгаа бүх хүчин төгөлдөр зэргэлдээг оруулаад матрицын массивт 0 гэж тохируулна уу.
  5. Бага зайг нэмэгдүүлэх.
  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-тэй хамгийн ойрын нүдний зайг олохын тулд 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

Хоёртын матрицад 1 байх хамгийн ойрын нүдний зайг олох C ++ код

#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