HINT

• đầu tiên ta tạo mảng hai chiều \(dp\) để lưu vị trí của các ô vuông, ta tạo mảng hai chiều \(f\) để lưu số cách đi đến ô \(dp[i][j]\)
• ta có công thức quy hoạch động:

\(f[0][1]=1\)

nếu $ dp[i][j]=\(\('\) * *#**\)'$ thì \(f[i][j]=0\)

nếu $ dp[i][j]='.'$ thì \(f[i][j]=(f[i-1][j]+f[i][j-1])\) * %*\(1e9+7\)

kết quả là \(f[h][w]\)

Reference AC code | \(O(h * w)\)time | \(O(h * w)\)space | DP-general

int main()
{
    cin>>h>>w;
    for(int i=1; i<=h; i++)
        for(int j=1; j<=w; j++)
            cin>>dp[i][j];
    f[0][1]=1;
    for(int i=1; i<=h; i++)
    {
        for(int j=1; j<=w; j++)
        {
            if(dp[i][j]=='#')
                f[i][j]=0;
            else
                f[i][j]=(f[i-1][j]+f[i][j-1])%mod; //mod=10000000007
        }
    }
    cout<<f[h][w];
}