{"id":2351,"date":"2020-07-29T07:33:57","date_gmt":"2020-07-29T07:33:57","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2351"},"modified":"2022-12-13T11:21:07","modified_gmt":"2022-12-13T11:21:07","slug":"nearest-cellpaid","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/nearest-cellpaid\/","title":{"rendered":"Nearest Cell(paid)"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Recursion<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT (SIMPLIFIED):<\/h3>\n
\n

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\u2212i2|+|j1\u2212j2|, 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.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
Input\n2\n3 3\n0 0 1 1 1 1 1 0 1\n4 4\n1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0\n\nOutput\n1 1 0 0 0 0 0 1 0 \n0 1 0 1 1 2 1 2 1 1 1 2 0 0 0 1 <\/code><\/pre>\n
OBSERVATION:<\/h3>\n
N=3  and M=3\n\nMatrix = \n\n[ 0 0 1 ]\n[ 1 1 1 ]\n[ 1 0 1 ]\n\nDistance for index (0,0) to the nearest 1 is at index (1,0)\n which is 1(1\u22120+0\u22120=1) so in distance matrix at index (0,0) input 1.\n\nDistance matrix = \n\n[ 1 1 0 ]\n[ 0 0 0 ]\n[ 0 1 0 ]<\/code><\/pre>\n
SOLVING APPROACH:<\/h3>\n
\n
A simple solution for this problem is to for each 0 in the matrix recursively check the nearest 1 in the matrix.<\/p>\n
An efficient solution<\/strong> for this problem is to use BFS<\/strong>. Here is the algorithm to solve this problem<\/p>\n<\/blockquote>\n
ALGO :\n For our BFS routine, we keep a queue, q to maintain the queue of cells to be examined next.\n\n We start by adding all the cells with 0s to q.\n\n Intially, distance for each 0 cell is 0 and distance for each 1 is INT_MAX, which is updated during the BFS.\n\n 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].<\/code><\/pre>\n
SOLUTIONS:<\/h3>\n
\t\t\t\t\t\t