ווייַטקייט פון די ניראַסט צעל מיט 1 אין אַ ביינערי מאַטריץ  


שוועריקייט לעוועל שווער
אָפט געבעטן אין אַקסענטורע אַמאַזאָן האָנייוועלל הסבק הולו טוויטטער
מענגע ברעט ערשטער זוך גראַפיק מאַטריץ ריי

פּראָבלעם סטאַטעמענט  

די פּראָבלעם "ווייַטקייט פון די ניראַסט צעל מיט 1 אין אַ ביינערי מאַטריץ" זאגט אַז איר האָט אַ ביינערי מאַטריץ(מיט בלויז 0 ס און 1 ס) מיט לפּחות איין 1. געפֿינען די ווייַטקייט פון די ניראַסט צעל מיט 1 אין די ביינערי מאַטריץ פֿאַר אַלע יסודות פון די מאַטריץ, דאָ די ווייַטקייט צווישן צוויי סעלז (קס 1, י 1) און (קס 2, י 2 ) איז | x2 - x1 | + | י 2 - י 1 |.

ביישפילן  

{
{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 און סטאָרד די ווייַטקייט אין די אַנס מענגע.
  3. דרוק די אַנס מענגע.
זע אויך
ריווערסינג די ערשטע ק עלעמענטן פון אַ ריי

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי = אָ (n2 * עם2)
ספעיס קאַמפּלעקסיטי = אָ (N * ב)
וווּ 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 סטאַרטינג פון אַלע די 1 אין די געגעבן מאַטריץ. די ווייַטקייט פון אַלע 1 ס איז נול און פֿאַר אַלע די שכייניש די מינימום ווייַטקייט איז מער ווי דעם.

  1. שאַפֿן אַ ריי פון קאָאָרדינאַטעס, וואָס איז געניצט צו קראָם די (רודערן, זייַל) פון אַן עלעמענט. שאַפֿן אַן מענגע אַנס פון גרייס זעלביקער ווי מענגע מאַטריץ.
  2. דורכפאָר אַלע עלעמענטן פון דער מאַטריץ און שטופּן די קאָואָרדאַנאַץ פון עלעמענטן וואָס זענען 1 אין דער ריי.
  3. יניטיאַליזירן אַ בייַטעוודיק ווייַטקייט ווי 0. די ריי איז נישט ליידיק איבערחזרן די סטעפּס 4 און 5.
  4. יניטיאַליזירן אַ בייַטעוודיק גרייס ווי די גרייס פון דער ריי. לויפן אַ שלייף פֿאַר איך יקוואַלז 0 צו גרייס (נישט אַרייַנגערעכנט). ביי יעדער יטעראַטיאָן קנאַל זיך אַן עלעמענט פֿון דער ריי. באַשטעטיק אַנס [רודערן] [קאָל] ווי מינדיסטאַנסע, און שטעלן אַלע די גילטיק אַדזשאַסאַנץ פון דעם עלעמענט וואָס זענען 0 אין די מאַטריץ מענגע און שטעלן זיי ווי 1 אין די מאַטריץ מענגע.
  5. ינקרעמענט מיניסטאַנסע.
  6. דרוק די אַנס מענגע.
זע אויך
געפֿינען די חילוק לעעטקאָדע לייזונג

קאַמפּלעקסיטי אַנלייסיס

צייט קאַמפּלעקסיטי = אָ (N * ב)
ספעיס קאַמפּלעקסיטי = אָ (N * ב)
וווּ n און m זענען די ראָוז און שפאלטן פון די געגעבן מאַטריץ ריספּעקטיוולי.

די אַלגערידאַם איז זייער ענלעך צו די BFS פֿאַר גראַפס, און אַזוי בלויז O (N * M) איז גענומען.

דערקלערונג

באַטראַכטן די בייַשפּיל,
{
{0, 1, 0}
{0, 0, 0}
{1, 0, 0}
}

ווייַטקייט פון די ניראַסט צעל מיט 1 אין אַ ביינערי מאַטריץשפּילקע

קאָדעקס

Java Code צו געפֿינען די ווייַטקייט פון די ניראַסט צעל מיט 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