CONCEPTS USED:

Recursion

DIFFICULTY LEVEL:

Easy

PROBLEM STATEMENT (SIMPLIFIED):

Rahul is stuck in a maze world, where the maze is a binary matrix of size NXM (each cell has value 0 or 1). To get out of this world he needs to calculate the distance to the nearest 1 for each cell in the maze. Distance between the two cells is calculated by |i1−i2|+|j1−j2|, where i1, j1 are the row number and column number of the current cell and i2, j2 are the row number and column number of the nearest cell having value 1.

See original problem statement here

For Example :

Input
2
3 3
0 0 1 1 1 1 1 0 1
4 4
1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0

Output
1 1 0 0 0 0 0 1 0 
0 1 0 1 1 2 1 2 1 1 1 2 0 0 0 1 

OBSERVATION:

N=3  and M=3

Matrix = 

[ 0 0 1 ]
[ 1 1 1 ]
[ 1 0 1 ]

Distance for index (0,0) to the nearest 1 is at index (1,0)
 which is 1(1−0+0−0=1) so in distance matrix at index (0,0) input 1.

Distance matrix = 

[ 1 1 0 ]
[ 0 0 0 ]
[ 0 1 0 ]

SOLVING APPROACH:

A simple solution for this problem is to for each 0 in the matrix recursively check the nearest 1 in the matrix.

An efficient solution for this problem is to use BFS. Here is the algorithm to solve this problem

ALGO :
 For our BFS routine, we keep a queue, q to maintain the queue of cells to be examined next.

 We start by adding all the cells with 0s to q.

 Intially, distance for each 0 cell is 0 and distance for each 1 is INT_MAX, which is updated during the Do online programming practice to know that an efficient solution for this problem is to use BFS.

 Pop the cell from queue, and examine its neighbours. If the new calculated distance for neighbour {i,j} is smaller, we add {i,j} to q and update dist[i][j].

SOLUTIONS:

#include<bits/stdc++.h>
using namespace std;

class graph
{
private:
    vector<int> g[10001];
    int n,m;

public:
    graph(int a, int b)
    {
        n = a;
        m = b;
    }

    // Function to create graph with N*M nodes
    // considering each cell as a node and each
    // boundary as an edge.
    void createGraph()
    {
        int k = 1;  // A number to be assigned to a cell

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                // If last row, then add edge on right side.
                if (i == n)
                {
                    // If not bottom right cell.
                    if (j != m)
                    {
                        g[k].push_back(k+1);
                        g[k+1].push_back(k);
                    }
                }

                    // If last column, then add edge toward down.
                else if (j == m)
                {
                    g[k].push_back(k+m);
                    g[k+m].push_back(k);
                }

                    // Else make edge in all four direction.
                else
                {
                    g[k].push_back(k+1);
                    g[k+1].push_back(k);
                    g[k].push_back(k+m);
                    g[k+m].push_back(k);
                }

                k++;
            }
        }
    }

    // BFS function to find minimum distance
    void bfs(bool visit[], int dist[], queue<int> q)
    {
        while (!q.empty())
        {
            int temp = q.front();
            q.pop();

            for (int i = 0; i < g[temp].size(); i++)
            {
                if (visit[g[temp][i]] != 1)
                {
                    dist[g[temp][i]] =
                            min(dist[g[temp][i]], dist[temp]+1);

                    q.push(g[temp][i]);
                    visit[g[temp][i]] = 1;
                }
            }
        }
    }

    // Printing the solution.
    void print(int dist[])
    {
        for (int i = 1, c = 1; i <= n*m; i++, c++)
        {
            cout << dist[i] << " ";
        }
        cout<<endl;
    }
};



int main()
{

    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        bool mat[n][m];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                cin>>mat[i][j];
        }
        graph g1(n, m);
        g1.createGraph();

        // To store minimum distance
        int dist[10001];

        // To mark each node as visited or not in BFS
        bool visit[10001] = { 0 };

        // Initialising the value of distance and visit.
        for (int i = 1; i <= m*n; i++)
        {
            dist[i] = INT_MAX;
            visit[i] = 0;
        }

        // Inserting nodes whose value in matrix
        // is 1 in the queue.
        int k = 1;
        queue<int> q;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (mat[i][j] == 1)
                {
                    dist[k] = 0;
                    visit[k] = 1;
                    q.push(k);
                }
                k++;
            }
        }

        // Calling for Bfs with given Queue.
        g1.bfs(visit, dist, q);

        // Printing the solution.
        g1.print(dist);

    }
    return 0;
}

Since, the new cells are added to the queue only if their current distance is greater than the calculated distance, cells are not likely to be added multiple times.

Space complexity:
O(r c). Additional O(r c)for queue.

Previous post Play Games 3
Next post Parallelograming(paid)

Leave a Reply

Your email address will not be published. Required fields are marked *