这道题用的是二维答案数组,最后只要对着坐标直接输出就行,但是,在数据处理和求状态转移方程上,这道题给本狗倒是挖了点坑...比如为啥小码君没把小蚂蚁直接踩死或者踩到左脚等等
开始正经讲题!
1,数据处理方面
这道题题面上说这只蚂蚁只能向右边和上面走,而且要从右下角走到左上角,要知道,C++的数组结构是从左上角往右下角扩大的,那如果真按照题面来写的话,将会极其繁琐...(可能你代码没敲完,键盘先起义了)所以我们要先把题面倒一下,让这只蚂蚁从左上角往右下角走,只能向左或向下移动,被踩掉的是左脚
2.状态转移方程
这道题的状态转移方程其实和蜜蜂路线那道题差不多,这只小 蚂蚁如果想要到右下角(此时我们已经把题面倒了一下),那就必须得到右下角上方的格子或左边的格子,根据加法原理并以此类推,除了可以一次到达的格子外,所有格子的路径总数都为上方和左方的格子路径数之和,即a[i][j]=a[i-1][j]+a[i][j-1];
3.敲键盘
现将一步到达的格子初始化,输入之后按照状态转移方程递推即可
记得开LONG LONG