演算法訓練之過河馬
- 一、題目
- 二、思路
- 三、題解
- 四、題目鏈接
一、題目
資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
在那個過河卒逃過了馬的控制以超級超級多的走法走到了終點之后，這匹馬表示它不開心了……
于是，終于有一天，它也過河了！
由于過河馬積累了許多的怨念，所以這次它過了河之后，再也沒有什么東西可以限制它，它可以自由自在的在棋盤上馳騁，一開始，它是在一個n行m列棋盤的左下角（1,1）的位置，它想要走到終點右上角（n，m）的位置，而眾所周知，馬是要走日子格的，可是這匹馬在積累了這么多怨念之后，它再也不想走回頭路——也就是說，它只會朝向上的方向跳，不會朝向下的方向跳，
那么，這匹馬它也想知道，它想從起點跳到終點，一共有多少種走法呢？
輸入格式
第一行兩個數n，m，表示一個n行m列的棋盤，馬最初是在左下角（1,1）的位置，終點在右上角（n，m）的位置，
輸出格式
輸出有一行，一個數表示走法數，由于答案可能很大，所以輸出答案除以1000000007所得的余數即可，
樣例輸入
4 4
樣例輸出
2
資料規模和約定
n<=100,m<=100
二、思路
如圖，我們理一下思路，從左下角跳到右上角，用一個二維陣列來存盤跳到每個點的總步數，我們來逆推，（其中2,3和3,2只可能是從1,1跳來的，），以黃點為例，他可能是A、B、C、D任意一點跳來的，然后，要判斷一下A、B、C、D在不在棋盤內，
然后題目說答案可能很大，輸出答案除以1000000007所得的余數即可，那為了防止爆掉，我們每加完一條路的總步數之后就取一遍余，
題目解法思路如上述，但是這里有一個我之前從來沒有注意過的問題，導致我一直只有90分，那就是我一直習慣于在main函式內宣告變數，，，
具體原因是在這篇博客里看的，詳情點擊傳送門，
其實就是說在main函式外面開一個陣列，他的記憶體分配在資料區里；如果在main函式內部開陣列，記憶體分配在堆疊區內，一般來說堆疊區的記憶體是比較小的，所以平常開一些小一點的陣列是沒問題的；但如果題目要求的陣列比較大，那就會出現爆出的問題，
三、題解
#include<iostream>
using namespace std;
int n,m;
int cb[105][105];
int main(){
cin>>n>>m;
cb[2][3] = cb[3][2] = 1;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(i-1 >=1 && j-2 >= 1)
{
cb[i][j] += cb[i-1][j-2];
cb[i][j] %= 1000000007;
}
if(i-2 >=1 && j-1 >= 1)
{
cb[i][j] += cb[i-2][j-1];
cb[i][j] %= 1000000007;
}
if(i-2 >=1 && j+1 <= m)
{
cb[i][j] += cb[i-2][j+1];
cb[i][j] %= 1000000007;
}
if(i-1 >=1 && j+2 <= m)
{
cb[i][j] += cb[i-1][j+2];
cb[i][j] %= 1000000007;
}
}
}
cout<<cb[n][m];
return 0;
}
四、題目鏈接
ALGO-981 過河馬
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/357033.html
標籤：其他