बाइनरी म्याट्रिक्समा १ भएको नजिकको सेलको दूरी


कठिनाई तह हार्ड
बारम्बार सोधिन्छ एक्सेंचर अमेजन हनीवेल एचएसबीसी Hulu twitter
एरे चौड़ाई पहिलो खोजी ग्राफ म्याट्रिक्स लाम

समस्या वक्तव्य

समस्या "बाइनरी म्याट्रिक्समा १ भएको नजिकको सेलको दूरी" बताउँछ कि तपाईंलाई बाइनरी दिइन्छ म्याट्रिक्स(केवल ० र १ सेकेन्ड सहित) कम्तिमा १ १ सहित। नजिकको सेलको दूरी पत्ता लगाउनुहोस् १ बाइनरी म्याट्रिक्समा म्याट्रिक्सका सबै तत्वहरूका लागि, यहाँ दुई सेलहरू (x0, y1) र (x1, y1) को बीच दूरी। ) | x1 - x1 | हो + | y2 - y2 |

उदाहरण

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

स्पष्टीकरण: हामी देख्न सक्छौं कि १ भएको कोषहरूको नतीजा म्याट्रिक्समा १ हुन्छ र सेलहरू १ को दूरीमा १ कोषहरू भएको। यी कक्षहरू १ उत्पादनको रूपमा हुन्छ र त्यस्तै दूरीहरू अन्य कोशिकाहरूको लागि गणना गरिएको छ।

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

भोली दृष्टिकोण

म्याट्रिक्सको प्रत्येक तत्व को लागी, पूरा ट्रान्सभर्स गर्नुहोस् म्याट्रिक्स र म्याट्रिक्समा कम से कम दूरी भएको सेल फेला पार्नुहोस्।

  1. एरे म्याट्रिक्सको जस्तो साइजको एर्रे एन्सेस बनाउँनुहोस्। दुई नेस्टेड लूपहरू चालु गर्नुहोस् म्याट्रिक्सको सबै तत्वहरू पार गर्न।
  2. म्याट्रिक्सको प्रत्येक एलिमेन्टको लागि म्याट्रिक्सको प्रत्येक एलिमेन्टलाई ट्र्यावर्स गर्न दुईवटा नेस्टेड लूपहरू चलाउनुहोस्, हामी यसलाई हालको एलिमेन्टको रूपमा गर्न सक्छौं सबै हालको तत्त्वहरू जुन १ हुन्, न्यूनतम दूरी तत्त्व फेला पार्नुहोस् र त्यो दूरीलाई एन्सेस एर्रेमा भण्डार गर्नुहोस्।
  3. उत्तर एर्रे प्रिन्ट गर्नुहोस्।

जटिलता विश्लेषण

समय जटिलता = O (n2 * मि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 ++ कोड

#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. एक सिर्जना गर्नुहोस् लाम Coordinates को, त्यो कुनै तत्वको (प ,्क्ति, स्तम्भ) भण्डारण गर्न प्रयोग गरिन्छ। सिर्जना गर्नुहोस् array एर्रे जस्तै आकारको उत्तरहरू म्याट्रिक्स.
  2. म्याट्रिक्सको सबै तत्वहरू बाट पार गर्नुहोस् र तत्त्वहरूको निर्देशांकहरू समेट्नुहोस् जुन लाममा १ छन्।
  3. एउटा चर मिनेटस्ट्यान्स ० को रूपमा आरम्भ गर्नुहोस्। जबकि पue्क्ति खाली दोहोर्याउने चरण 0 र not छैन।
  4. लामको आकारको रूपमा एक चर आकार प्रारम्भ गर्नुहोस्। I बराबर ० आकारको लागि लूप चलाउनुहोस् (समावेश गरिएको छैन)। प्रत्येक पुनरावृत्तिमा लामबाट तत्व पप आउट गर्नुहोस्। Ans [प ]्क्ति] [कोल] लाई minDistance को रूपमा सेट गर्नुहोस्, र यो तत्वको सबै मान्य अace्कहरू मिलाउनुहोस् जुन म्याट्रिक्स एर्रेमा ० छन् र तिनीहरूलाई १ को रूपमा म्याट्रिक्स एर्रेमा सेट गर्नुहोस्।
  5. वृद्धि minDistance।
  6. उत्तर एर्रे प्रिन्ट गर्नुहोस्।

जटिलता एनालिसिस

समय जटिलता = O (n * m)
ठाउँ जटिलता = O (n * m)
जहाँ n र m क्रमशः दिइएका म्याट्रिक्सको प .्क्ति र स्तम्भहरू हुन्।

एल्गोरिथ्म ग्राफको लागि बीएफएससँग धेरै मिल्दोजुल्दो छ र यसैले ओ (एन * एम) समय मात्र लिइएको छ।

स्पष्टीकरण

उदाहरणलाई विचार गर्नुहोस्,
{
{0, 1, 0}
{0, 0, 0}
{1, 0, 0}
}

बाइनरी म्याट्रिक्समा १ भएको नजिकको सेलको दूरी

कोड

जावा कोड एक बाइनरी म्याट्रिक्समा १ भएको नजिकको सेलको दूरी पत्ता लगाउन

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 ++ कोड

#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