بائنري ميٽرڪس ۾ 1 کي ويجهي سيل جي مفاصلو


تڪليف جي سطح سخت
بار بار پڇڻ ۾ Accenture Amazon Honeywell HSBC Hulu Twitter
ڪيريو ماني لاءِ پهرين ڳولا گراف قائم ٿينديون پنگتي حيثيت رکي ٿو

مسئلي جو بيان

مسئلو ”ويجهي سيل جو فاصلو بائنري ميٽرڪس ۾ 1 هجڻ“ ٻڌائي ٿو ته توهان کي هڪ بائنري ڏني وئي آهي ميٽرڪس(صرف 0s ۽ 1s تي مشتمل آهي) گهٽ ۾ گهٽ هڪ 1 سان. ميٽرڪس جي سڀني عنصرن جي بائنري ميٽرڪس ۾ 1 سان ويجهن خاني جو فاصلو ڳوليو ، هتي ٻن خاني جي وچ ۾ فاصلو ) آھي | x1 - x1 | + | y2 - y2 |.

مثال

{
{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}
}

نائي اچڻ وارو

ميٽرڪس جي هر عنصر لاءِ س theي طرح پيچيده ڪيو ميٽرڪس ۽ ميٽر کي گهٽ ۾ گهٽ فاصلو هجڻ سان گڏ ڳوليو.

  1. ساڳيو ئي آرسي ميٽرڪس جي هڪ ايري سائيز ٺاهيو. ميٽرڪس جي سڀني عنصرن کي ڇڪڻ لاءِ ٻه جوڙيل لوپ هلائڻ.
  2. ميٽرڪس جي هر عنصر لاءِ ، ميٽرڪس جي هر عنصر کي پار ڪرڻ لاءِ وڌيڪ ٻه ٻلندڙ لوپ هلائيندا ، اچو اسان موجوده عنصر وانگر. سڀني موجوده عنصرن لاءِ جيڪي 1 آهن ، گهٽ ۾ گهٽ مفاصلو عنصر ڳوليو ۽ اهو فاصلو بند ڪريو.
  3. اين ايس آرٽ پرنٽ ڪيو.

پيچيدگي تجزيي

وقت جي پيچيدگي = اي (اين2 * ايم2)
خلائي پيچيدگي = اي (ن * م)
جتي ن ۽ م د ترتيب ڏنل ميٽرڪس جي قطار ۽ ڪالم آهن.

جئين اسان ميٽرڪس ۾ هر هڪ جي لاءِ س matي مئٽرڪ مان گذري رهيا آهيون. هي ٺاهيل الگورٿم کي وڌيڪ وقت جي پيچيدگين ۾ هلائڻ لاءِ. خلائي پيچيدگي صرف پيداوار کي اسٽور ڪرڻ جي ڪري آهي ، پر الگورتھم پاڻ کي مستقل جڳهه جي ضرورت آهي. جيڪڏهن اسان سڌي طرح ٻاھران ڇپائي سگهون ها ته پوءِ اها خلائي پيچيدگي گهٽجي وڃي ها.

ڪوڊ

جاوا ڪوڊ ڳولڻ لاءِ ويجهڙائي واري سيل جو فاصلو بائنري ميٽرڪس ۾ 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

بائنري ميٽرڪس ۾ 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

ڪوشان وارو رستو

بهتر طريقو اهو آهي ته ڏنل مئٽرڪس ۾ سڀني 1s کان شروع ڪري BFS ڪيو وڃي. سڀني 1s جي مفاصلي کي صفر آھي ۽ سڀني ويجھو سڀني لاءِ گھٽ فاصلو ھڪ کان وڌيڪ آھي.

  1. هڪ ٺاهيو پنگتي حيثيت رکي ٿو تنظيمن جو ، جيڪو هڪ عنصر جي (قطار ، ڪالمن) کي ذخيرو ڪرڻ لاءِ استعمال ڪيو ويندو آهي. هڪ ٺاهيو صف سائز جي برابر جيتري ميٽرڪس.
  2. ميٽرڪس جي سڀني عنصرن کي ڇڪڻ ۽ انهن عناصر جي همراه کي ڌڪڻ جيڪي 1 ۾ قطار ۾ آهن.
  3. شروعاتي طور هڪ متغير منٽ فاصلو جي طور تي 0. جئين قطار خالي نه آهي ٻيهر وارين قدم 4 ۽ 5.
  4. قطار جي سائز جي حساب سان ھڪڙي متغير شڪل کي شروعاتي طور تي شروع ڪريو. مون لاءِ لوپ هليو ته مون وٽ 0 جي برابر آهي (شامل نه آهي) هر حرڪت ۾ قطار مان هڪ عنصر ٻاهر نڪري ويو. مائن ڊيزائن جي طور تي اين ايس [قطار] [ڪولي] کي سيٽ ڪريو ، ۽ هن عنصر جا سمورا جائز ايڊٽيون انٽڪس ڪريو جيڪي ميٽرڪس جي صف ۾ 0 آهن ۽ انهن کي ميٽرڪس جي صف ۾ 1 جي طور تي مقرر ڪيو آهي.
  5. وڌ ۾ وڌ مفاصلو.
  6. اين ايس آرٽ پرنٽ ڪيو.

پيچيدگي ايناليسس

وقت جي پيچيدگي = اي (ن * م)
خلائي پيچيدگي = اي (ن * م)
جتي ن ۽ م د ترتيب ڏنل ميٽرڪس جي قطار ۽ ڪالم آهن.

الگورتھم 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

بائنري ميٽرڪس ۾ 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