Map Representation

For maximum RAM efficiency, it is best to represent each partition with a bit (1 means a partition exists, 0 means a partition doesn't exist). The program needs two arrays of bits, one to represent horizontal partitions and one to represent vertical partitions.

The boundary can be implied. This means there are only 15 columns of vertical walls and 15 rows of horizontal walls. Each column or row has 16 partitions. The total number of bytes required is $\frac{2 \times 15 \times 16}{2}$, or 60 bytes.

Once again, you can linearize the walls. However, the linearization now relies on which direction you want to look from a cell. For example, the east wall of a cell at row $r$ and column $c$ has a linear index of $16c+r$ in the vertical partition array. The west wall of the same cell has a linear index of $16(c-1)+r$ in the vertical partition array. The north wall of the same cell has a linear index of $16r+c$ in the horizontal partition array. The south wall of the same cell has a linear index of $16(r-1)+c$ in the horizontal partition array.

For efficiency, you can directly compute the byte number as 2*c + r/8 for the east partition of a cell, and use r % 8 to compute the bit number in that byte. Recall that most compilers are smart enough to use shifts (instead of multiply and divide) and bitwise and (instead of modulus).

The boundary partitions are special cases because they are always there. For example, all cells on column 0 have west partitions. If you use the previous equation to computer the linearized bit number of the west wall of a column zero cell, it yields a negative number.

It is best to write some subroutines to abstract the handling of partitions. In particular, you can define two subroutines:

• int existWall(int row, int col, int dir) checks if a partition exists at the dir direction of a cell on row row and column col. dir enumerates the four directions (0 for north, 1 for east and etc.)
• void setWall(int row, int col, int dir, int setClear) sets or clears a wall. If setClear is non-zero, the subroutine sets a wall. If setClear is zero, the subroutine clears a wall.

Once you have these two functions, you can implement the logic to find reachable neighbors of a cell by checking which direction(s) does/do not have a parition blocking.