This is a classic problem of dynamic programming with bit masks.

The first problem you are trying to fill a 4xN board, this can be done iterating over columns, notice that if you are going to fill column K, you need to know the state of column K-1, K-1 may be full or may have some holes, for each hole you need to place an horizontal domino in column K, the trick is to have a bitmask representation for the state of column K-1 and iterate over all possible valid bitmasks for column K.

In the second problem N*M <= 100, this means than min(N, M) <= 10, this allows you to use the same approach as before.