Very frequently we'll encounter problems like "Find the path in a matrix with minimum distance/cost", so the question is how can we solve it easily and also efficiently? This note is not intended to be a definitive guide by any means, but it only attempts to give a general idea/direction, so that when we meet such a problem, we know where to start figuring it out.
- We use "matrix" and "grid" interchangeably in this note.
- This note assumes you have experience with basic grid traverse patterns like BFS and DFS.
- OK, let's start.
- First thing is about the matrix. We need to make sure that there's a matrix so that we can traverse it, otherwise we might have to build it. For example, in this shortest path in a hidden grid and this minimum path cost in a hidden grid, the grids are hidden. So we need to build it first, either with a new 2d array, or a map-like data structure (
current cell -> neighbor cells). The end goal is when we traverse the grid, we know how to find the neighbor cells. Here I do recommend building a new 2d array, because most of the cases, it'll be easier to write the logic and also faster, because the "current cell -> neibghor cells" info is inherently available. And with the map approach, we have to do extra encode and decode logic, which is a pain. More details like why we use DFS to paint the grid, and how to work with the coordinates are available in those two notes. - Now we have a grid. What next?
- Second thing is about the start and the target. Indeed, we need to know where to start and where to stop. Most of the time, these info are given, however, if not, we can easily traverse the grid to find it. So, no need to panic.
- Cool, now we have the start and target info, then what?
- Third thing is about how we move forward. Basically, there are two things we need to pay attention to. One thing is, obviously, if we meet some kind of obstacles, or moving out of the boundary, or we don't have the "keys" we need (see this example), we cannot move forward with that path. Second thing is about how many steps we can move forward. Normally, we just move one step at a time, like moving up, down, left or right. However, sometimes, for example in the maze question, the ball won't stop rolling until it meets the wall. Honestly, it's not doing something dramatically different. It just moves forward with multiple steps at a time, comparing with the previous 1 step movement. That's easy, we can always have a helper function to find out all "neighbors" by rolling in different directions, until we have to stop. Also if needed, we can do some logic inside the helper function to check each cell we meet while rolling.
- Awesome, we know how to move forward, so let's continue to the "target" then?
- Well, not so fast. The fourth thing is about how we represent the state. At the least, we need a state like
[x, y], which represents our current position in the grid. If we need the shortest distance or minimum cost, we'll add that to the state as well, like[x, y, current distance] or [x, y, current cost]. Another thing worth mentioning is that sometimes we can remove the obstacles, that will also become part of the state, to represent how many obstacles we can still remove, i.e.,[x, y, current distance, obstacles can be removed], like in shorest path in a grid with obstacles elimination. Also there's some Dynamic Programming idea in it too, we can discuss that in the future. A third case is an extra state like "keys we have" in this question shortest path to get all keys, you can find more details about how to represent the keys with a compression trick. - So we got the grid, the start and target, and the state, we're finally ready to move to the target and find the shortest path?
- Almost there, lol. The fifth thing is about the the weight of steps we take. Depends on the question's description, the weight of the steps we take can change our solution. So, a) if every step has same cost, we can start doing BFS by exploring one "level" at a time (exhaustively) until we reach the target. And in this case, BFS will guarantee us a shortest/minimum solution, because we are simply trying every possibilities a step at a time, and each new level is one step further. The first time you meet the target is definitely in the shorest path; b) if every step has possibly different costs, then we need a priority queue, because, priority queue will allow you to pick the most promising state first every time with good efficiency (
O(logh),hbeing the height of the tree containing all states), and also this is the underlying idea of Dijkstra algorthm. We might will visit this algorithm in other questions too. - Finally, we can safely and confidently move forward to the target, since we got everything we need.
- Let me know if this makes sense to you, too.
- Thanks for reading.