Making a Maze
InterviewTime limit1sMemory limit128 MB
Find the minimum number of black cells to convert to white so a path exists from top-left to bottom-right of an n x n grid, using 0-1 BFS or Dijkstra.
- Level
Medium5 of 10
- Topics
- BFS, Shortest path, Graph
- Solved
- No attempts yet
Problem
There are n^2 rooms arranged as an n × n grid. Each room is either white or black. You may enter white rooms, and there is a door between two white rooms that share a side. A black room is blocked and cannot be entered as it is.
The starting room is the top-left cell, and the ending room is the bottom-right cell. Both of these rooms are always white. If necessary, you may change black rooms into white rooms so that a path from the start to the end exists.
Find the minimum number of black rooms that must be changed to white rooms to make it possible to travel from the starting room to the ending room. If the path already exists, the answer is 0.
Input
The first line contains the number of rooms in each row, n. (1 ≤ n ≤ 50)
Each of the next n lines contains a string of length n. Every character is either 0 or 1; 0 means a black room, and 1 means a white room.
Output
Print the minimum number of black rooms that must be changed to white rooms so that the ending room can be reached from the starting room.