Call a square "covered by a red square" if the first condition holds; otherwise, say that it is "covered by a blue square."

Without loss of generality, suppose that $(1,1)$ is covered by a red square. Then find the minimum $j$ such that $(1,j)$ is covered by a blue square. In this case, $(1,j-1)$ must be red, no squares to the right of $(1,j-1)$ on the same row must be red, and every square with second coordinate less than $j$ is covered by a red square. In this case, we can assign every uncolored square with second coordinate less than $j$ a color of red or white as we choose. Now,

- If $j=N+1$ then we're done.
- Otherwise, $(1,j)$ is covered by a blue square and we can run the solution recursively on the remaining $N\times (N+1-j)$ sub-rectangle. Find the minimum $k$ such that $(k,j)$ is covered by a red square, and continue.

In general, an assignment of squares to be covered by either red or blue corresponds to a down-right path from $(1,1)$ to some square $(x,y)$ that satisfies $x=N+1$ or $y=N+1$. The colors of the squares that are just before where the path changes direction are fixed, while every other square has two options (white, or the color it is covered by).

Dhruv Rohatgi's code:

#include <iostream> #include <algorithm> #include <cstdio> using namespace std; #define MOD 1000000007 int N; long long p = 500000004LL; char A[2005][2005]; char B[2005][2005]; int r[2005][2005]; int b[2005][2005]; int psr[2005][2005]; int psb[2005][2005]; int main() { freopen("sprinklers2.in","r",stdin); freopen("sprinklers2.out","w",stdout); cin >> N; for(int i=0;i<N;i++) cin >> (A[i+1]+1); for(int i=2;i<=N+1;i++) if(A[i-1][1] == '.') b[i][0] = psb[i][0] = p; for(int j=1;j<=N;j++) if(A[1][j] == '.') r[1][j] = psr[1][j] = p; for(int i=2;i<=N+1;i++) for(int j=1;j<=N;j++) { if(A[i][j] == '.') { r[i][j] = (p*psb[i][j-1])%MOD; // cout << "red " << i << ',' << j << ": " << r[i][j] << '\n'; } if(A[i-1][j+1] == '.') { b[i][j] = (p*psr[i-1][j])%MOD; // cout << "blue " << i << ',' << j << ": " << b[i][j] << '\n'; } psr[i][j] = (psr[i-1][j] + r[i][j])%MOD; psb[i][j] = (psb[i][j-1] + b[i][j])%MOD; } int ans = (psr[N][N] + psb[N+1][N])%MOD; for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) if(A[i][j]=='.') ans = (2LL*ans)%MOD; cout << ans << '\n'; }