Distance of Nearest Cell having 1
BFS & DFS Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Finding the distance of the nearest 1 in a binary grid for each cell, Breadth-First Search, Graph Traversal, Queue, Matrices, Two-dimensional Array Traversal, Time Complexity, Space Complexity, Distance Calculation, complexity analysis, queue, matrix traversal, distance metric, bfs, Grid as a Graph.
Problem Statement: Given a binary grid of size N x M, where 1 represents an occupied cell and 0 represents an empty cell. For each cell in the grid, find the distance to the nearest cell containing a 1. The distance between two cells (r1, c1) and (r2, c2) is calculated as |r1 r2| + |c1 c2| (Manhattan distance). Input Specification: The first line contains two integers N and M, the number of rows and columns in the grid. The next N lines each contain M integers, representing the binary grid. Output Specification: Output an N x M grid where each cell (i, j) contains the distance from (i, j) to the nearest 1. Constraints: 1 <= N, M <= 500 Grid cells will contain either 0 or 1. It is guaranteed that at least one '1' is present in the grid. Sample Test Cases: Example 1: Input: Output: Explanation: The '0' at (0,1) is at a distance of 1 from '1' at (0,0). The '0' at (1,0) is at a distance of 1 from '1' at (0,0) or (1,1) or (2,0). The '0' at (1,2) is at a distance of 1 from '1' at (1,1) or (0,2). The '0' at (2,1) is at a distance of 1 from '1' at (2,0) or (1,1). The '0' at (2,2) is at a distance of 2 from '1' at (1,1). Example 2: Input: Output: