题目描述

就像人喜欢玩跳房子一样，农夫约翰的牛也发明了一种供他们玩耍的变种跳房子。

虽然这些重量接近一吨的笨重生物每次玩跳房子都会让牛棚遭受灾难性的破坏，但是奶牛们仍然乐此不疲的每天下午坚持游戏。

游戏在一个 R×C 的方格矩阵中进行，其中每个方格都用蓝色或红色进行着色。

奶牛从左上角的方格开始，通过一系列跳跃移动到右下角的方格结束。

奶牛在跳跃时，需满足：

将要跳入的格子的颜色必须与当前所在格子的颜色不同。
将要跳入的格子的所在行必须在当前所在格子的所在行的下方。
将要跳入的格子的所在列必须在当前所在格子的所在列的右方。
请帮助奶牛计算它们共有多少种不同的跳法，可以从左上角跳到右下角。

算法

(暴力)

#include<bits/stdc++.h>
using namespace std;
const int M=20;
int a[M][M],S[M][M],ans=0,r,c;
void doit(int xx,int yy,int y) { //当前坐标(xx,yy),y目标位置颜色
    if(xx==r&&yy==c)
        return ;
    if(a[xx][yy]^y) ans++;
    for(int i=1; i<=r; i++)
        for(int j=1; j<=c; j++)
        {
            if(a[i][j]^a[xx][yy])
            doit(i,j,y); 
        }
}
int main() {
    scanf("%d%d", &r, &c);
    for(int i=1; i<=r; i++)
        for(int j=1; j<=c; j++) {
            char k;
            cin>>k;
            if(k=='R')
                a[i][j]=1;
            else
                a[i][j]=0;
        }//初始化：r-->1  b-->0
    int ed=a[r][c];//起点与终点
    doit(1,1,ed);
    printf("%d\n",ans);
    return 0;
}