Grids

Grid problems are very common. It's probably no surprise; it's much easier to think of space as an infinite grid of cells, as opposed to a continuous collection of points. Modelling space as a grid can simplify computations and solutions to problems.

For example, you probably encountered grid-based board games, or tile-based video games. It's a convenient way of chopping up the whole map into neat little square tiles, making graphics easier to render, and making the game logic much simpler. For example, collision problems can be handled easily by just requiring that there is at most one unit/building at every tile at any time, whereas in non-tile-based games, complicated algorithms might need to be employed.

So let's discuss how to represent grids and how to perform some simple operations on them.

Rectilinear grids

You probably know what a grid is already, but in case you don't know, simply imagine a graphing paper. Or a chessboard. Those are grids.

Actually, those are rectilinear grids to be more precise. There are other kinds of grids such as hexagonal grids and triangular grids. We will study those at some point.

The most natural way to represent these grids is a two-dimensional (2D) array, or an array of arrays. For example, say we want to represent this map:

.......
..##...
..#..#.
.#..##.
...##..
.#.....

If we represent the character # as $1$ and . as $0$, then we can represent this as the 2D array:

  1. int grid[6][7] = {
  2. {0,0,0,0,0,0,0},
  3. {0,0,1,1,0,0,0},
  4. {0,0,1,0,0,1,0},
  5. {0,1,0,0,1,1,0},
  6. {0,0,0,1,1,0,0},
  7. {0,1,0,0,0,0,0},
  8. }

You can also use a 2D array of characters. It's really up to you!

At this point, we mention a few important things. First, in the above example, the grid was hardcoded, meaning it was typed directly into the code. But most problems require you to take the grid from the input. How do we do this? Here's one way: Let's first assume that the dimensions of the grid are given as the first two integers in the input, for example,

6 7
.......
..##...
..#..#.
.#..##.
...##..
.#.....

Then we can take this input with some code like this:

  1. // get the dimensions
  2. int r, c;
  3. cin >> r >> c;
  4. // allocate the 2D array
  5. int **grid = new int*[r];
  6. // loop across all rows
  7. for (int i = 0; i < r; i++) {
  8. // allocate the current row
  9. grid[i] = new int[c];
  10. // take the current row from input
  11. string s;
  12. cin >> s;
  13. // populate the current row
  14. for (int j = 0; j < c; j++) {
  15. if (s[j] == '#') {
  16. grid[i][j] = 1;
  17. } else {
  18. grid[i][j] = 0;
  19. }
  20. }
  21. }

(Be careful about which number is the width, and which is the height! Read the input section carefully.)

Next, in many cases, you might get confused about the order of the indices. For example, should it be grid[i][j], or grid[j][i]? grid[x][y] or grid[y][x]? This is especially tricky if you need to traverse your grid. For example, what is the cell to the left of grid[x][y]? Is it grid[x-1][y], or grid[x][y-1]? Or grid[x][y+1]?

In these cases, it really depends on your implementation, i.e., on whether you assign the first index to be the horizontal or vertical coordinate. Just choose one and be consistent with it! One way to keep track of things is to draw the grid on paper and write the corresponding coordinates in the cells. Then use this as your guide during coding! After some practice, you'll get used to it.

Grid movement

Now that we have taken the grid from input into memory, let's play with it! What can we do, though? Lot's of things!

For example, suppose we want to see if two cells are reachable from each other within a map, like in the following:

...#..#....#....#..
.S#.T...#..#..#.#..
#..###.#.#...#..#.#
.#..#..#.#..#..#...
##..#..#..#...#..#.
...#.##..#..###..##
..#....#..#....#...
..#.##..#...##..###
..#...#..#.#..#....
...##.#.......#..##
.#.....#.#..#.#.#..
#.###.#..#.#.#.#...
....#..#..##....##.
.#..#...#...#.#....

How do we know if there's a path from S to T? Knowing how to do this is useful, for example, when trying solve a maze.

But first, let's be clear on the allowed movements. In some variants, only up, down, left and right movements are allowed. In others, diagonal movements are allowed. Still in others, more fancy movements are allowed like “knight’s move” or “bishop’s move”.

Some versions also allow wrapping around the edges of the map to emerge to the other side, like in overworld maps of some 2D games.

In our simple example, let's keep the allowed movements to just the four cardinal directions: up, down, left and right. Also, let's say the grid is surrounded by walls on all sides, so there's no wrap-around.

To begin, let's describe movement within the grid. But to do so, as mentioned above, we need to choose a convention on what $i$ and $j$ on grid[i][j] means. We can use the most natural one, which is that $i$ represents the row number and $j$ represents the column number. (In fact the input-taking code above uses this convention.)

As mentioned above, drawing this on paper would help. Let's do that now:

$$\require{cancel} \require{enclose} \begin{array}{r|rrrrrr} & j=0 & j=1 & j=2 & j=3 & j=4 & \ldots \\ \hline i=0 & (0,0) & (0,1) & (0,2) & (0,3) & (0,4) & \ldots \\ i=1 & (1,0) & (1,1) & (1,2) & (1,3) & (1,4) & \ldots \\ i=2 & (2,0) & (2,1) & (2,2) & (2,3) & (2,4) & \ldots \\ i=3 & (3,0) & (3,1) & (3,2) & (3,3) & (3,4) & \ldots \\ i=4 & (4,0) & (4,1) & (4,2) & (4,3) & (4,4) & \ldots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \\ \end{array}$$

With such an image, it becomes easy to see some spatial relationships between cells. For instance:

Diagonal movement is also easy to describe.

With this guide, we can now return to our original problem of checking if a path exists from S to T. To answer the problem, we will need to traverse the grid.

Grid traversal

How do we figure out which cells are reachable from S? If you've dabbled in MS Paint, then you'll see that what we really need is some sort of flood fill operation. You can sort of imagine it as dropping a bucket of paint on cell S and letting it flood the region until all cells reachable from S have been painted. For example, in the above grid, if we start a flood fill on S, then this is the result:

~~~#~~#~~~~#~~~~#..
~S#~~~~~#~~#~~#~#..
#~~###~#~#~~~#~~#.#
.#~~#~~#~#~~#~~#...
##~~#~~#~~#~~~#..#.
~~~#~##~~#~~###..##
~~#~~~~#~~#~~~~#...
~~#~##~~#~~~##~~###
~~#~~~#~~#~#~~#~~~~
~~~##~#~~~~~~~#~~##
~#~~~~~#~#~~#~#~#..
#.###~#~~#~#.#.#...
....#~~#~~##....##.
.#..#~~~#~~~#.#....

Now, as you can see, the cell T was flooded, which means T is indeed reachable from S!

So how do we do this flood fill? A simple way is to construct another 2D array, which we can call vis, that will keep track of which cells have been visited by the fill operation. Specifically, vis[i][j] will be true if cell $(i, j)$ is reachable from S. Initially, this array contains all false, except the cell corresponding to S.

Then, we simply do recursion! Here's one way:

  1. void flood_fill(int i, int j) {
  2. // starts a flood fill on cell (i, j)
  3. vis[i][j] = true; // mark this cell as visited
  4. //- try left
  5. if (j > 0 && !vis[i][j-1] && grid[i][j-1] != '#') {
  6. flood_fill(i, j-1);
  7. }
  8. //- try right
  9. if (j < c-1 && !vis[i][j+1] && grid[i][j+1] != '#') {
  10. flood_fill(i, j+1);
  11. }
  12. //- try up
  13. if (i > 0 && !vis[i-1][j] && grid[i-1][j] != '#') {
  14. flood_fill(i-1, j);
  15. }
  16. //- try down
  17. if (i < r-1 && !vis[i+1][j] && grid[i+1][j] != '#') {
  18. flood_fill(i+1, j);
  19. }
  20. }

By calling flood_fill(I, J) where $(I, J)$ is the location of S, the array vis will be filled correctly! Here's an example of how to kick off the flood fill:

  1. void flood_fill_on_S() {
  2. // find where the 'S' is
  3. for (int i = 0; i < r; i++) {
  4. for (int j = 0; j < c; j++) {
  5. if (grid[i][j] == 'S') {
  6. flood_fill(i, j);
  7. return; // exit the method
  8. }
  9. }
  10. }
  11. }

Here are a couple of points to remember:

Now, with the vis array filled, we can now answer the question: T is reachable from S if and only if vis[i][j] is true, where $(i, j)$ is the coordinates of T!

To be continued...