馬が川を渡るのを止める(C++)


碁盤のA点には川を渡る卒がいて、目標のB点まで歩く必要があります.歩行のルール:下へ、または右へ.同時に碁盤上のC点には相手の馬があり、その馬がいる点とジャンプして一歩で達する点を相手の馬の制御点と呼ぶ.そのため「馬が川を渡る卒」と呼ばれている.
碁盤は座標で表され,A点(0,0),B点(n,m),同様に馬の位置座標が与えられる必要がある.
今、卒がA点からB点に到達できる経路の数を計算するように要求されます.馬の位置が固定されていると仮定して、卒が一歩歩いて馬が一歩歩いているわけではありません.
Input Format
1行の4つの正の整数で、それぞれB点座標と馬の座標を表します.100%のデータに対して,1≦n,m≦20,0≦馬の座標≦20であった.
Output Format
すべてのパス・バーの数を表す整数.
Input Example
6 6 3 3
Output Example
6
問題解決の考え方:
2 D配列のa[i][j]の値は、座標が(i,j)の点からB点(終点)までのすべてのパス数を格納する.
2 D配列の右下方向左上から行単位で列単位でスキャンして値を割り当てます.
状態遷移方程式:a[i][j]=a[i][j+1]+a[i+1][j].
初期化:a[n-1][m]とa[n][m-1]の値は1です.終点a[n][m]まで1つの道しかないからです.
境界処理:2 D配列のn行目とm列目の各配列要素の値は1です.終点まで1つの道しかないからです.
特殊条件処理:
a[i][j+1]とa[i+1][j]が馬が一歩で到達できる位置である場合はa[i][j]=maxとなる.
a[i][j+1]は、馬が一歩で到達できる位置である場合にはa[i][j]=a[i+1][j]となる.
a[i+1][j]は、馬が一歩で到達できる位置である場合にはa[i][j]=a[i][j+1]となる.
ACコード:
#include
#include
#define maxn 10000  //                 10000
using namespace std;
int main()
{
    int n,m;long int a[21][21];int xm,ym;//xm,ym      
    memset(a,0,sizeof(a));//          0
    cin>>n>>m>>xm>>ym;
    a[xm][ym]=maxn;//        maxn
    int i,j;
    for(j=ym-1;j<=ym+1;j+=2)//           maxn
        for(i=xm-2;i<=xm+2;i+=4)
        {
            if(i<0||j<0)
                continue;
            else
                a[i][j]=maxn;  
        }
    for(i=xm-1;i<=xm+1;i+=2)//             maxn
        for(j=ym-2;j<=ym+2;j+=4)
        {
            if(i<0||j<0)
                continue;
            else
                a[i][j]=maxn;
        }

    for(i=n;i>=0;i--)
        for(j=m;j>=0;j--)
        {
            if(a[i][j]==maxn)//           
                continue;
            if(i==n||j==m)//    ,       ,   ,        
                a[i][j]=1;
            else if(a[i][j+1]==maxn&&a[i+1][j]==maxn)
                a[i][j]=maxn;
            else if(a[i][j+1]==maxn&&a[i+1][j]!=maxn)
                a[i][j]=a[i+1][j];
            else if(a[i][j+1]!=maxn&&a[i+1][j]==maxn)
                a[i][j]=a[i][j+1];
            else
                a[i][j]=a[i][j+1]+a[i+1][j];//    
        }
cout<