走格子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