Grid Coloring_牛客博客

http://codeforces.com/group/NVaJtLaLjS/contest/242532

You have an m-by-n grid of squares that you wish to color. You may color each square either redor blue, subject to the following constraints:
• Every square must be colored.
• Colors of some squares are already decided (red or blue), and cannot be changed.
• For each blue square, all squares in the rectangle from the top left of the grid to that square
must also be blue.
Given these constraints, how many distinct colorings of the grid are there? The grid cannot be
rotated.
Input
The first line of input consists of two space-separated integers m and n (1 ≤ m, n ≤ 30).
Each of the next m lines contains n characters, representing the grid. Character ‘B’ indicates
squares that are already colored blue. Similarly, ‘R’ indicates red squares. Character ‘.’ indicates
squares that are not colored yet.
Output
Print, on a single line, the number of distinct colorings possible.
For the first sample, the 6 ways are:
BB BB BR BR BB BB
BB BR BR BR BR BB
BR BR BR RR RR RR
2017 Pacific Northwest Region Programming Contest 23
Sample Input and Output
3 2
…
B.
.R
6
7 6
…
…B
.B…R.
…
…B…
.R…
…R…
3
2 2
R.
.B
0

题意：给定一个矩阵，初始含B、R、.三种，.表示待填。矩阵需要满足的条件是填B的格子的左上（包括左、上）方全部都是B。
求矩阵填满的方案数。
思路：B左上都必须是B，那么对称地，R的右下方都必须是R，考虑同一行，必定是左i个是B，右m-i个是R。
那么，设 $f (i, j)$ 为前i行，左j个是B，右边是R的方案数。则 $f (i, j) = \sum f (i - 1, k), k \in [j, m]$

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll n,m,f[35][35];
char s[35][35];

int main()
{
   // freopen("input.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            bool ok=1;
            for(int k=j;k>=1;k--)if(s[i][k]=='R')ok=0;
            for(int k=j+1;k<=m;k++)if(s[i][k]=='B')ok=0;
            if(ok)
                if(i==1)f[i][j]=1;
                else for(int k=j;k<=m;k++)f[i][j]+=f[i-1][k];
        }
    }
    ll sum=0;
    for(int j=0;j<=m;j++)sum+=f[n][j];
    cout<<sum<<endl;
    return 0;
}