Hello, and welcome. My name is William and today we're going to talk about using a breadth first search to find the shortest path on a grid. This is going to be a really fun video because we're going to solve a problem, and I'm going to teach you a bunch of handy tricks when doing graph theory on grids. Before we get started, I highly recommend my video introducing the breadth first search algorithm. Make sure you understand the basics of a breadth first search for continuing because we will be building off the topics of those concepts. There should be a link in the description for the last video.

The motivation behind why we're learning about grids in this video is that a surprising number of problems can easily be represented using a grid, which a lot of the times turns into a graph theory problem grids are interesting because they're a form of implicit graph, which means that we can determine a nodes neighbors based on our location within the grid. For instance, finding a path through a maze is a form of a grid problem you're trying to get from one side of the maze to the other. Well, you need to find a path. It's a pathfinding problem. Or perhaps you're a person trying to navigate your way through obstacles such as trees, rivers, and rocks to get to a particular location. And this can be modeled using a grid, and in turn, we end up using graph theory to navigate around.

A common approach to solving graph theory problems on grids is to first convert the grid to a familiar format, such as an adjacency list or an adjacency matrix so we can easily work with them. However, this isn't always the most efficient technique, but we'll get to that. Suppose we have a grid on the left and we want to represent it as both an adjacency list And adjacency matrix, what do we do first? First, you should label all the cells in the grid with the numbers zero through n non inclusive, where n is the product of the number of rows and columns. So in this grid on the left, there are six cells. So I labeled each cell with the numbers zero through six, nine inclusive, then we actually want to construct an adjacency list and an adjacency matrix.

Based off this grid. The adjacency list doesn't require any setup because it's simply a map that we initialize, but the adjacency matrix requires us to initialize a matrix of size six by six to represent our graph. There are six rows and six columns in the new adjacency matrix, because it's how many nodes that are in the grid we're trying to represent. Assuming edges are unweighted and cells connect to left right up and down. Node zero connects with node one One and node two, which we reflected in the adjacency list, and adjacency matrix on the right, then node one connects to node zero and node three, node two to node 03, and four, node three, with nodes one, two, and five, and so on. And that's basically how you convert a grid to an adjacency list or an adjacency matrix.

Once we have an adjacency list or an adjacency matrix, we are able to easily run whatever specialized graph algorithm we need to solve our problems such as finding the shortest path finding connected components etc. However, transformations between graph representations can usually be avoided due to the structure and the nature of a grid. Let me explain. Suppose where the red ball in the middle and we know we can move left, right up and down to reach adjacent cells. Well, mathematically if we're the red ball at the row column coordinate r comma C, we can add the row vectors minus 101 comma 00, comma one and zero comma minus one to reach all the adjacent cells. If the problem you're trying to solve allows moving diagonally, then you can also use the row vectors minus one minus one minus 1111, and one minus one.

Using row vectors makes it easy to access neighboring cells from the current row column position. First, define the direction vectors for north south, east and west broken down into their row column components. Then what we want to do is loop over each direction vector and add it to the current position here I iterate I from zero to For Non inclusive because we only have four directions, then add the row direction to the current row to make our our the variable representing the new row, and then add the column direction to the current column to make cc the new column position. So the new position on the grid rrr comma cc is an adjacent cell. However, it might not be an adjacent cell if we're on the border of the grid, and the new position is out of bounds. So we check that the new coordinate is within our grid by making sure that the new row column position is greater than or equal to zero and doesn't exceed the number of rows and columns of our grid respectively.

So if those two checks pass, then we know that the new position are our comma cc is a neighboring cell of our current position where the red ball was our comma seat So in summary, this technique is really nice, really easy to code and actually naturally extends to higher dimensions. So let's solve a shortest path problem on a grid using the direction vector technique we just learned about. So here's an abridged problem statement that you might encounter during an interview or in a programming competition. And it goes as follows. Suppose you're trapped inside a 2d dungeon and need to find the quickest way out. The dungeon is composed of unit cubes, which may or may not be filled with rock.

It takes one minute to move one unit north, south, east, or west. You cannot move diagonally and the maze is surrounded by solid rock on all sides. This problem statement is an easier version of the problem Dungeon Master on the caddis online judge see the problem link in the scription the dungeon is a grid of size R by C and you start at the node with an S character, and there is an exit at the cell with an E. A cell full of rock is indicated by a pound sign or a hashtag, and empty cells are represented using a.in. This particular setup it's possible to escape the dungeon using this particular route highlight in green. Remember that we want the shortest path to escape dungeon, not just any path. Our approach is going to be to do a breadth first search from the start node until we reach the end node and count the number of cells we traverse during that process.

However, it might not be possible to exit the dungeon if we cannot reach the exit. So we'll have to be mindful of that. So like in any breadth first search, we need to start by visiting our start node and adding it to queue assuming we've already found the coordinate of our star node within the grid when added to the queue, then we visit the adjacent unvisited neighbors and add them to the queue as well. And continue this process all the while avoiding adding rock cells to the queue. So I'll let the animation play And meanwhile, try and predict which cells will be visited next. All right, after we find our end cell, we know how many steps it takes to get from the start to the end.

Notice that we didn't even visit all the cells in the grid. The bottom right cell is still unvisited. So it's possible that we terminate early if you're interested in actually finding the path itself rather than just the number of things apps that takes to escape the dungeon, then you'll need to keep track of the previously visited node for each node. Go and re watch the last video. If you need a refresher on how to do that, I want to talk a little bit about the way we're representing states in our breadth first search. So far, we have been storing the next x y position in the queue as an XY pair.

This works well but requires an array or an object wrapper to store the coordinate values. In practice, this can require a lot of packing and unpacking values to and from our cue. Let's look at an alternative approach, which also scales well in higher dimensions, and in my opinion, requires less setup and effort. So the alternative approach I'm suggesting is to use one cue through each dimension. So in a three dimensional grid, you would have one key For each of the x, y and z dimensions, suppose we're in queueing the coordinate x one y ones that one, then we would simply place each coordinate in their respective queues. So the x coordinate goes in the x q, the y goes in its own y, q, and so on.

As we need to keep and queuing different positions, we simply keep filling up these queues this way. This contrasts the approach of simply having one queue with each of the components packed away inside an object. The one thing we have to be mindful about however, is that when we either n keyword dq elements, you need to mq and dq elements from each of the queues all at the same time. So when I dq or pull elements from the queue, I need to remove an element from each of these queues. I prefer this representation When working with multi dimensional coordinates, which is why I want to share it, try it out and see if it works for you. So now that we have all the knowledge we need, we can solve the dungeon problem, let's look at some pseudocode assume that I have already read in the input matrix into memory and did some pre processing to find the coordinate of the starting node.

The first two variables are the constants R and C the number of rows and columns in the input matrix following this is m, the input character matrix of size R by C. Next are two variables S, R and S. See the row column position of the starting node will need this to start our breadth first search our Q and c q or q q data structures that represent the rho Q and the column q will be n queuing and D queuing elements from during the breadth first search this next set of videos balls is to keep track of the number of steps taken to reach the exit move count will actually track the number of steps taken nodes left in layer tracks how many nodes we need to dq before taking a step and nodes in next layer tracks how many nodes we added in the breadth first search expansion, so that we can update nodes left and layer accordingly.

In the next iteration, this will make more sense soon reached and tracks whether or not we have reached the end cell marked with an E. We're also going to make use of a visited matrix the same size as the input grid to track whether or not a cell has been visited since we do not want to visit a cell multiple times. And lastly, I define the north south, east and west direction vectors. To solve the dungeon problem. This is all the code we'll need to execute our breadth first search and reach the exit. The first thing I do is add the start cells row and column values to the row Q and column Q, then don't forget to mark the start cell as visited because we don't want to go there. Again, we're not done our breadth first search until both of our cues are empty.

I checked the size of the row q is greater than zero, but you can also check the size of the column q is greater than zero since their sizes should always be in sync. Then since I know the queues aren't empty, I can dq the current position from the queues as the row position R and the column position C. Then I check if we've reached the dungeon exit by checking if the current character in the grid is an E. If it is then mark that we've reached the exit and break out early. Otherwise, we're not done exploring and we want to add all the valid neighbors of the current node to the queue. I wrote a function called export neighbors that do just that. Let's have a look. Here we are inside the Explore neighbors method.

This is where we'll be using the direction vector technique we learned about earlier. Since cells have four directions we care about north, south, east and west I loop I from zero to four non inclusive, compute the new coordinate RR comma CC, by adding the direction vector to the current position, make sure the new position is actually within the grid because we could end up with positions like zero comma minus one which is out of bounds. Even if the new position is within the grid that does not guarantee that is a valid position. So position might already have been visited previously, or it could be a blocked off cell such as a cell that isn't traversable and full of rock. If both of those conditions aren't true, then we can cue the new position to visit it later. When in QA a new position we are going to visit Make sure to mark it as visited now, so that it doesn't get added to the queue multiple times in the future.

Also increment the number of nodes in the next layer, which we'll be needing shortly. This next block of code is used to track the number of steps we took. Getting to the dungeon exit. Every time we finished a layer of nodes, we increment the number of steps taken. We know how many nodes are in each layer because we kept track of that in the Explore neighbors method. When the number of nodes in the current layer reaches zero, we know to increment the move count.

At the end, if we are able to reach the exit, we return the move count, otherwise we return minus one to indicate that the dungeon exit was not reached. So in summary, things we learned in this session video on how to represent a grid as an adjacency list and an adjacency matrix, how to use direction vectors to visit neighboring cells, we explored an alternative way of representing multi dimensional coordinates with multiple queues. And lastly, we looked at how to use a breadth first search on a grid to find the shortest path between two cells. Thank you for watching. Please like this video if you learn something and subscribe for more mathematics and computer science videos.