« back

Fill the Matrix

Tags : geeksforgeeks, bfs, cpp, medium

Problem Statement - link #

Given a matrix with dimensions N x M, entirely filled with zeroes except for one position at co-ordinates X and Y containing ‘1’. Find the minimum number of iterations in which the whole matrix can be filled with ones.

Note: In one iteration, ‘1’ can be filled in the 4 neighbouring elements of a cell containing ‘1’.

Your Task:

You don’t need to read input or print anything. Your task is to complete the function minIterations() which takes the dimensions of the matrix N and M and the co-ordinates of the initial position of ‘1’ ie X and Y as input parameters and returns the minimum number of iterations required to fill the matrix.

Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)

Examples #

Example 1:

Input:
N = 2, M = 3
X = 2, Y = 3
Output: 3 

Explanation: 3 is the minimum possible 
number of iterations in which the
matrix can be filled.

Example 2:

Input:
N = 1, M = 1
X = 1, Y = 1 
Output: 0

Explanation: The whole matrix is 
already filled with ones.

Constraints #

Solutions #


class Solution{
public:
    int minIteration(int N, int M, int x, int y){    
        // code here
        vector<vector<int>> vis(N + 1, vector<int> (M + 1, 0));
        vis[x][y] = 1;
        queue<pair<int, int>> q;
        q.push({x, y});
        int res = 0;
        while(q.size()) {
            int cur_size = q.size();
            while(cur_size--) {
                auto p = q.front(); 
                q.pop(); 
                x = p.first, y = p.second;
                if(x > 1 && vis[x - 1][y] == 0) {
                    q.push({x - 1, y});
                    vis[x - 1][y] = 1;
                }
                if(y > 1 && vis[x][y - 1] == 0) {
                    q.push({x, y - 1});
                    vis[x][y - 1] = 1;
                }
                if(x < N && vis[x + 1][y] == 0) {
                    q.push({x + 1, y});
                    vis[x + 1][y] = 1;
                }
                if(y < M && vis[x][y + 1] == 0) {
                    q.push({x, y + 1});
                    vis[x][y + 1] = 1;
                }
            }
            if(q.size()){
                res++;                
            }

        }
        return res;
    }
};