走格子DP，（棋盘DP）递归法

牛牛有一个nm的迷宫，对于迷宫中的每个格子都为’R’,‘D’,'B’三种类型之一‘R’表示处于当前的格子时只能往右边走’D’表示处于当前的格子时只能往下边走，而’B’表示向右向下均可以走 峩们认为迷宫最左上角的坐标为(1,1)，迷宫右下角的坐标为(n,m)除了每个格子有向右移动以及向下移动的限制之外，你也不能够走出迷宫的边界 牛牛现在想要知道从左上角走到右下角不同种类的走法共有多少种，请你告诉牛牛从(1,1)节点移动到(n,m)节点共有多少种不同的移动序列请你輸出方案数对109+710^9+7109+7取余数后的结果。 我们认为两个移动序列是不同的当且仅当移动序列的长度不同，或者在某一步中采取了不同的移动方式
第一行输入两个正整数n,m(1≤n,m≤50)(1 \leq n,m \leq 50)(1≤n,m≤50)表示迷宫的大小是n行m列。接下来n行每行输入一个长度为m的字符串，字符串中仅包含大写字母’D’,‘R’,‘B’
输出一行一个整数，表示方案数对109+710^9+7109+7取余数后的结果**

1.搞一个二维数组储存数据，再搞一个二维数组（用于记录每个位置的路径并保证是走到右下角）右下角放1，其余为-1从左上角开始，用递归的方式遇到不同的位置，每走一步记录该位置到右下角的路径数目到该②维数组中（遇到相同的位置直接引用，降低复杂度）
2.从右下角到左下角思路同上，但每次算路径是都要考虑另外两个位置的情况所以我没用该方法
1.二维数组存放路径要用long long ，并且算的时候就要先模（不然wa到你心痛，呜呜呜）不要在输出时处取模
2.为了缩短程序运行時间，是用数组存放路径的值如果只用变量，（超时，，呜呜呜）

发布了7 篇原创文章 · 获赞 0 · 访问量 161