מרחק התא הקרוב ביותר שיש בו 1 במטריצה ​​בינארית


רמת קושי קשה
נשאל לעתים קרובות אקסנצ'ר אמזון בעברית Honeywell HSBC Hulu טויטר
מערך רוחב החיפוש הראשון גרף מַטרִיצָה תור

הצהרת בעיה

הבעיה "המרחק של התא הקרוב ביותר שיש 1 במטריצה ​​בינארית" קובעת שמקבלים בינארי מַטרִיצָה(המכיל רק 0s ו- 1s) עם לפחות אחד 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. צור מערך ans בגודל זהה למטריצת המערך. הפעל שתי לולאות מקוננות כדי לחצות את כל האלמנטים של המטריצה.
  2. עבור כל אלמנט במטריצה, הפעל שני לולאות מקוננות נוספות כדי לחצות כל אלמנט של המטריצה, הבה נוכל לעשות זאת כאלמנט הנוכחי. עבור כל האלמנטים הנוכחיים שהם 1, מצא את אלמנט המרחק המינימלי ושמור את המרחק הזה במערך ans.
  3. הדפס את מערך ans.

ניתוח מורכבות

מורכבות זמן = O (n2 * M2)
מורכבות בחלל = O (n * m)
כאשר n ו- m הם השורות והעמודות של המטריצה ​​הנתונה בהתאמה.

מכיוון שאנחנו עוברים את כל המטריצה ​​עבור כל אחד מהתאים במטריצה. זה גורם לאלגוריתם לפעול במורכבות זמן גבוהה יותר. מורכבות החלל היא רק בגלל אחסון הפלט, אך האלגוריתם עצמו דורש מקום קבוע. אם פשוט היינו מדפיסים את הפלט, אז גם מורכבות החלל הזו הייתה מופחתת.

קופונים

קוד Java כדי למצוא מרחק של תא קרוב ביותר שיש בו 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 החל מכל 1s במטריצה ​​הנתונה. המרחק של כל ה- 1 הוא אפס ועבור כל הסמוכים המרחק המינימלי הוא אחד יותר מזה.

  1. צור תור של קואורדינטות, המשמש לאחסון (שורה, עמודה) של אלמנט. ליצור מערך ans בגודל זהה למערך מַטרִיצָה.
  2. חצו את כל האלמנטים של המטריצה ​​ודחפו את הקואורדינטות של האלמנטים שהם 1 לתור.
  3. אתחל מינימום מרחק משתנה כ- 0. התור אינו ריק חזור על שלבים 4 ו -5.
  4. אתחל גודל משתנה כגודל התור. הפעל לולאה עבור i שווה 0 לגודל (לא כלול). בכל איטרציה פוצץ אלמנט מהתור. הגדר את ans [row] [col] כ- minDistance, וצף את כל המתאמים החוקיים של אלמנט זה שהם 0 במערך המטריצה ​​והגדר אותם כ- 1 במערך המטריצה.
  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 במטריצה ​​בינארית

קופונים

קוד Java כדי למצוא מרחק של תא קרוב ביותר שיש לו 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