2016做砸了的小网站,wordpress 微信导航菜单,中国新闻社总编辑,湖州吴兴建设局网站链接#xff1a; 时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 131072K#xff0c;其他语言262144K 64bit IO Format:%lld 题目描述 赛时提示#xff1a;保证出发点和终点都是空地 帕秋莉掌握了一种木属性魔法 这种魔法可以生成一片森林 时间限制C/C 1秒其他语言2秒 空间限制C/C 131072K其他语言262144K 64bit IO Format:%lld 题目描述 赛时提示保证出发点和终点都是空地 帕秋莉掌握了一种木属性魔法 这种魔法可以生成一片森林类似于迷阵但一次实验时帕秋莉不小心将自己困入了森林 帕秋莉处于地图的左下角出口在地图右上角她只能够向上或者向右行走 现在给你森林的地图保证可以到达出口请问有多少种不同的方案
答案对2333取模
输入描述: 第一行两个整数m , n表示森林是m行n列 接下来m行每行n个数描述了地图 0 - 空地 1 - 树无法通过 输出描述: 一个整数表示答案 示例1 输入
3 3
0 1 0
0 0 0
0 0 0输出
3题解 经典的递推式记忆化搜索 从左下角↙走到右上角↗ 式子 dp [ i] [ j ] dp [ i - 1 ] [ j ] d p [ i ] [ j - 1 ] 意义当前这个点ij是由他的左侧i-1j和下侧ij-1走到的 话说出题人真好还提供了快读模板 代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int mod2333;
const int maxn3004;
bool a[maxn][maxn];
ll dp[maxn][maxn];
templateclass Tinline void read(T res)
{
char c;T flag1;
while((cgetchar())0||c9)if(c-)flag-1;resc-0;
while((cgetchar())0c9)resres*10c-0;res*flag;
}int main()
{int n,m;read(m);read(n);for(int i1;im;i)for(int j1;jn;j){read(a[i][j]);if(imj1)dp[i][j]1;}for(int im;i1;i--)for(int j1;jn;j){if(a[i][j]1)continue;else if(i!n||j!1)dp[i][j](dp[i1][j]dp[i][j-1])%mod;}coutdp[1][n];return 0;
}
