Luogu P 1022过河卒(DP)

P 1022川を渡る
タイトルの説明
碁盤のA点には川を渡る卒がいて、目標のB点まで歩く必要があります.歩行のルール:下へ、または右へ.同時に碁盤上のC点には相手の馬があり、その馬がいる点とジャンプして一歩で達する点を相手の馬の制御点と呼ぶ.そのため「馬が川を渡る卒」と呼ばれている.
碁盤は座標で表され、A点(0,0)、B点(n,m)(n,mは20を超えない整数)と同様に馬の位置座標が与えられる必要がある.
今、卒がA点からB点に到達できる経路の数を計算するように要求されます.馬の位置が固定されていると仮定して、卒が一歩歩いて馬が一歩歩いているわけではありません.
にゅうしゅつりょくけいしき
入力形式:
1行の4つのデータで、それぞれB点座標と馬の座標を表します.
出力フォーマット:
すべてのパス・バー数を表すデータ.
入出力サンプル
サンプル#1を入力:

6 6 3 3

出力サンプル#1:

6

説明
結果は大きいかもしれません!
 
この問題を読み始めたとき、思いついたのはdfsだった.しかし改めて考えてみると、絶対にTLEになります.
だからdpを使う必要があります.実はとても簡単なdpです.
卒は(0,0)から始まり、下または右に2つの移動方式しかありません.
遷移方程式はf[x][y]+=max(f[x-1][y],f[x][y-1])x,y>=0と決定できる.
f[x][y]は、(0,0)から(x,y)までの最大パス数を表す
境界条件もx>0またはy>0を良く決定する.   f[0][0] = 1;
次に、コードを見てみましょう.
　

 1 #include 
 2 
 3 char map[25][25];
 4 long long f[25][25];    //        0
 5 
 6 int main()
 7 {
 8     int ex, ey, mx, my, nmx, nmy;
 9     scanf("%d%d%d%d", &ex, &ey, &mx, &my);
10     //  8      
11     int mmx[9] = {-1, -2, -2, -1, 1, 2, 2, 1};
12     int mmy[9] = {-2, -1, 1, 2, 2, 1, -1, -2};
13     //          
14     map[mx][my] = 1;
15     //             1
16     for(int i=0; i<8; i++)
17     {
18         nmx = mx+mmx[i];
19         nmy = my+mmy[i];
20         if(nmx>=0 && nmy>=0 && nmx<=ex && nmy<=ey)
21             map[nmx][nmy] = 1;
22     }
23     
24     f[0][0] = 1;    //    
25     for(int i=0; i<=ex; i++)
26     {
27         for(int j=0; j<=ey; j++)
28         {
29             if(i && !map[i][j])    //   i   0      RE
30                 f[i][j] += f[i-1][j];
31             if(j && !map[i][j])    //j  
32                 f[i][j] += f[i][j-1];
33         }
34     }
35     //ex ey      f[ex][ey]   0,0        
36     printf("%lld", f[ex][ey]);
37     return 0;
38 }

 
転載先:https://www.cnblogs.com/yBaka/p/7365618.html