傳送門

因為小兵只能往右走和往下走

所以動態轉移方程為map[i][j]=map[i-1][j]+map[i][j-1]

感覺上。。是很經典的。

題目描述

棋盤上AAA點有一個過河卒，需要走到目標BBB點。卒行走的規則：可以向下、或者向右。同時在棋盤上CCC點有一個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。因此稱之為“馬攔過河卒”。

棋盤用坐標表示，AAA點(0,0)(0, 0)(0,0)、BBB點(n,m)(n, m)(n,m)(nnn, mmm為不超過202020的整數)，同樣馬的位置坐標是需要給出的。

現在要求你計算出卒從AAA點能夠到達BBB點的路徑的條數，假設馬的位置是固定不動的，并不是卒走一步馬走一步。

輸入輸出格式

輸入格式：

一行四個數據，分別表示BBB點坐標和馬的坐標。

輸出格式：

一個數據，表示所有的路徑條數。

輸入輸出樣例

輸入樣例#1： 復制 6 6 3 3 輸出樣例#1： 復制 6

說明

結果可能很大！

AC源碼：

?

#include<iostream> #include<cstdio> #include<cstring> int mx[9]={0,1,1,-1,-1,2,2,-2,-2},my[9]={0,2,-2,2,-2,1,-1,1,-1}; long long map[21][21]={0}; using namespace std; int main() {int m,n,x,y;scanf("%d%d%d%d",&m,&n,&x,&y);map[0][0]=1;for(register int i=0;i<=n;i++)for(register int j=0;j<=m;j++){if(j)map[i][j]+=map[i][j-1];if(i)map[i][j]+=map[i-1][j];for(register int f=0;f<9;f++)if(j==x+mx[f]&&i==y+my[f]){map[i][j]=0;break;}}printf("%lld\n",map[n][m]); }

?

?

?

轉載于:https://www.cnblogs.com/JCRL/p/9922458.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的经典动态规划之过河卒【洛谷 P1002】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。