11349: 【原1349】新跳房子

题目

题目描述

author: Rui Yang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1349

Description

John特别喜欢跳房子的游戏，于是他发明了一种游戏：

这个游戏是基于R*C(2 <= R <= 15, 2 <= C <= 15)的格子中，每个格子被染成红色或者蓝色。牛们从左上角开始移动，目标是右下角的格子，移动的每一步只有当满足以下条件的时候才是合法的：

1)你跳向的格子与你现在所在的格子颜色不同；

2)你跳向的格子的行数必须大于你目前所在格子的行数；

3)你跳向的格子的列数必须大于你目前所在格子的列数；

请帮助计算，从左上角到右下角一共有多少条合法的跳跃序列

Input Format

第一行包括两个整数R和C，接下来的R行每行有C个字符（'R'或者'B'）。其中，R代表红色，B代表蓝色

Output Format

输出从左上角到右下角所有的可能跳跃方法的数量。

Sample Input:

4 4
RRRR
RRBR
RBBR
RRRR

Sample Output:

3

yyong119's solution

#include <cstdio>
#define MAX_N 20
using namespace std;
int r, c;
int f[MAX_N][MAX_N];
char map[MAX_N][MAX_N];
inline int read_RB() {
    char ch = getchar();
    while (ch != 'R' && ch != 'B') ch = getchar();
    return ch;
}
int main() {
    scanf("%d %d", &r, &c);
    for (register int i = 0; i < r; ++i)
        for (register int j = 0; j < c; ++j)
            map[i][j] = read_RB();
    f[0][0] = 1;
    for (register int bx = 1; bx < r; ++bx)
        for (register int by = 1; by < c; ++by)
            for (register int ax = 0; ax < bx; ++ax)
                for (register int ay = 0; ay < by; ++ay)
                    if (map[ax][ay] != map[bx][by])
                        f[bx][by] += f[ax][ay];
    // for (register int i = 0; i < r; ++i) {
    //     for (register int j = 0; j < c; ++j)
    //         printf("%d ", f[i][j]);
    //     printf("\n");
    // }
    printf("%d", f[r - 1][c - 1]);
    return 0;
}