ចម្ងាយនៃក្រឡាដែលនៅជិតបំផុតមាន 1 នៅក្នុងម៉ាទ្រីសគោលពីរ


កម្រិតលំបាក រឹង
សួរញឹកញាប់ Accenture ក្រុមហ៊ុន Amazon Honeywell ធនាគារ HSBC ក្រុមហ៊ុន Hulu ក្នុង Twitter
អារេ ការស្វែងរកដំបូង ក្រាប ម៉ាទ្រីស ជួរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ ចំងាយនៃកោសិកាដែលនៅជិតបំផុតមាន ១ នៅក្នុងម៉ាទ្រីសគោលពីរ” ចែងថាអ្នកត្រូវបានគេអោយលេខគោលពីរ ម៉ាទ្រីស(មានផ្ទុកតែ ០ និង ១) ដែលមានយ៉ាងហោចណាស់ ១។ រកចម្ងាយនៃក្រឡាដែលនៅជិតបំផុតមាន ១ នៅក្នុងម៉ាទ្រីសគោលពីរចំពោះធាតុទាំងអស់នៃម៉ាទ្រីសនៅទីនេះគំលាតរវាងកោសិកា ២ (x១, ១) និង (x២, y0) ) គឺ | x1 - x1 | + | y1 - y1 | ។

ឧទាហរណ៍

{
{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. ព្រីនជួរអារេ។

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា = ឱ (ន។ )2 * ម2)
ភាពស្មុគស្មាញនៃលំហ = O (n * ម)
ដែល n និង m ជាជួរដេកនិងជួរឈរនៃម៉ាទ្រីសដែលបានផ្តល់រៀងៗខ្លួន។

ចាប់តាំងពីយើងកំពុងឆ្លងកាត់ម៉ាទ្រីសទាំងមូលសម្រាប់កោសិកានីមួយៗនៅក្នុងម៉ាទ្រីស។ នេះធ្វើឱ្យក្បួនដោះស្រាយដំណើរការក្នុងពេលវេលាស្មុគស្មាញជាង។ ភាពស្មុគស្មាញនៃអវកាសគឺដោយសារតែការរក្សាទុកលទ្ធផលប៉ុន្តែក្បួនដោះស្រាយដោយខ្លួនវាតម្រូវឱ្យមានទំហំថេរ។ ប្រសិនបើយើងបានបោះពុម្ពលទ្ធផលយ៉ាងសាមញ្ញនោះភាពស្មុគស្មាញនៃលំហនេះក៏ត្រូវបានកាត់បន្ថយដែរ។

លេខកូដ

កូដចាវ៉ាដើម្បីរកចម្ងាយនៃក្រឡាដែលនៅជិតបំផុតមាន ១ នៅក្នុងម៉ាទ្រីសគោលពីរ

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. បង្កើត ជួរ នៃកូអរដោនេដែលត្រូវបានប្រើដើម្បីទុក (ជួរដេកជួរឈរ) នៃធាតុមួយ។ បង្កើត អារេ ទំហំនៃទំហំដូចគ្នានឹងអារេ ម៉ាទ្រីស.
  2. ឆ្លងកាត់ធាតុទាំងអស់នៃម៉ាទ្រីសហើយរុញកូអរដោនេនៃធាតុដែលមានលេខ 1 ចូលជួរ។
  3. ចាប់ផ្តើមអថេរតូចអថេរជា ០ ខណៈពេលដែលជួរមិនមែនជាជំហានដដែលៗជំហាន ៤ និង ៥ ។
  4. ចាប់ផ្តើមទំហំអថេរដែលជាទំហំនៃជួរ។ ដំណើរការរង្វិលជុំសម្រាប់ i ស្មើនឹង 0 ទៅនឹងទំហំ (មិនរាប់បញ្ចូល) ។ នៅរាល់ការនិយាយឡើងវិញកើតឡើងពីជួរ។ កំនត់ ans [ជួរ] [col] ជា minDistance និងតំរែតំរឹមទាំងអស់ដែលមានសុពលភាពនៃធាតុនេះគឺ ០ ក្នុងអារេម៉ាទ្រីសហើយកំណត់វាជា ១ ក្នុងអារេម៉ាទ្រីស។
  5. បង្កើនភាពធន់។
  6. ព្រីនជួរអារេ។

ភាពស្មុគស្មាញ Anlaysis

ស្មុគស្មាញពេលវេលា = O (n * ម)
ភាពស្មុគស្មាញនៃលំហ = O (n * ម)
ដែល n និង m ជាជួរដេកនិងជួរឈរនៃម៉ាទ្រីសដែលបានផ្តល់រៀងៗខ្លួន។

ក្បួនដោះស្រាយគឺស្រដៀងនឹង BFS សម្រាប់ក្រាហ្វហើយដូច្នេះមានតែពេលវេលា O (N * M) ប៉ុណ្ណោះដែលត្រូវបានគេយក។

ការពន្យល់

ពិចារណាឧទាហរណ៍
{
{៧, ៨, ៩}
{៧, ៨, ៩}
{៧, ៨, ៩}
}

ចម្ងាយនៃក្រឡាដែលនៅជិតបំផុតមាន 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 ++ ដើម្បីស្វែងរកចម្ងាយនៃក្រឡាដែលនៅជិតបំផុតមាន ១ នៅក្នុងម៉ាទ្រីសគោលពីរ

#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