Problem Explanation
We are given an rectangular grid where we start at the cell (0, 0) and we have to reach the right bottom cell (N_x, N_y). In each move we can move to an adjacent cell which includes (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1), (i + 1, j + 1), (i + 1, j - 1), (i - 1, j + 1), (i - 1, j - 1). We are also given m circles with r radius. we cannot travel to a square in the grid if it is touching a circle. We have to tell if we can reach the bottom right cell or not.
Approach
We are going to use bfs using queue to check if we can reach the bottom right cell or not. We will check the cells in the circles by the Euclidian formula and mark them visited so we can’t visit them during the bfs. Now we start with the first cell and push all the cells adjacent to the current cell which are not visited, in the queue. And continue bfs until we reach the bottom right cell or cover every reachable cell.