Grid Coloring

This problem asks us the number of ways to color a grid in red and blue such that for every blue square, any square up and to the left is also blue. It also "fixes" some squares.

First, lets ignore the fixed squares, since we'll need to solve the problem when none are fixed anyway.

The typical solution to problems like this is a DP of X by Y where you try either X or Y for the given square, and then recurse on the remaining rectangles. That doesn't work as nicely here since the rectangles are not independent (due to blue square rules). We could try to figure out some sort of state explosion, but this is difficult.

Instead, lets thing of what a solution looks like. When we color the grid, we will see that the whole thing is divided such that the upper left triangle is blue and the lower right is red. We just need to find the number of ways to make this division. This can be done by finding the number of paths from the left hand side of the grid to the top of the grid using only movements to the right and up. Since we are moving up and right, we have a DAG, which can be topologically sorted, which gives us a clean ordering on which to process!

1. initialize the node in the lower left hand corner to 1
2. create a "dummy" row above the top row
3. draw an edge from each node to it's right and top neighbors
4. process nodes in topological sort order
5. each time you process a node, add it's value to it's two children
6. use longs....the number could be long

The value in the far right of the "dummy" row is the number of distinct paths the blue "boundary can take.

Dealing with fixed squares is a simple modification:

1. if there is a red square up and to the left of a blue square, there are no colorings
2. remove edges from your topological sort graph which would bring you to a node which cannot be a boundary node (aka above and left any forced blue square)

One can note that this is equivalent to a DP solution where dp[i][j] is the number of ways to color the rectangle from 0->j where the boundary of the blue area in column j is i.