0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0

new_grid[i][j] is dependent on
  i) old_grid[i][j],
 ii) old_grid[i][j+1],
iii) old_grid[i+1][j]
 iv) old_grid[i+1][j+1]

If exactly one of the above values are 1, then new_grid[i][j] will be 1, else 0.

1 1
0 0

1 0 1
0 0 0
0 0 0

1 0 1
0 0 0
1 1 1

newGrid: 0 1 0
         0 0 0

oldGrid 1: _ 0 1 _
           _ 0 0 _
           _ _ _ _

oldGrid 2: _ 1 0 _
           _ 0 0 _
           _ _ _ _

oldGrid 3: _ 0 0 _
           _ 1 0 _
           _ _ _ _

oldGrid 4: _ 0 0 _
           _ 0 1 _
           _ _ _ _

newGrid: 1 1 0
         0 0 0

oldGrid 1: 1 0 _ _
           0 0 _ _
           _ _ _ _

oldGrid 2: 0 1 _ _
           0 0 _ _
           _ _ _ _

oldGrid 3: 0 0 _ _
           1 0 _ _
           _ _ _ _

oldGrid 4: 0 0 _ _
           0 1 _ _
           _ _ _ _

oldGrid 5: _ 1 0 _
           _ 0 0 _
           _ _ _ _

oldGrid 6: _ 0 1 _
           _ 0 0 _
           _ _ _ _

oldGrid 7: _ 0 0 _
           _ 1 0 _
           _ _ _ _

oldGrid 8: _ 0 0 _
           _ 0 1 _
           _ _ _ _

oldGrid 1.1: 1 0 1 _
             0 0 0 _
             _ _ _ _

numberOfSolutions = numberOf1s * 4 * 2^(oldGridSize-4) - overlappingSolutionsCount
numberOfOverlappingSolutions * 2^(oldGridSize-4-overlapAreaSize)

function countOverlappingSolutions(newGrid: an MxN matrix) {
    result = 0
    oldGridSize = (M+1) * (N+1)
    for each pair of 1s in the newGrid:
        let manhattanDistance = manhattan distance between the 1s in the pair
        let overlapAreaSize = 0

        if the 1s are in the same row or column
            if manhattanDistance == 1:
                overlapSize = 2
        else if manhattanDistance == 2
            overlapAreaSize = 1

        result += 2^(oldGridSize -4 -overlapAreaSize)

    return result
}

let newGrid be a MxN matrix
let numberOf1s = number of 1s in newGrid
let oldGridSize = (M+1) * (N+1)

result = numberOf1s * 4 * 2^(oldGridSize - 4) - countOverlappingSolutions(newGrid)