ACMテーマ——馬が川を渡る

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

6 6 3 3

サンプル出力
6
 
どう見ても、検索問題のようで、DFSを直接書いた.果敢な時間超過.コードは次のとおりです.

//     ——    
using namespace std;
int MAP[20][20];
int n, m, mx, my, cnt;
int dx[] = {1,0}, dy[] = {0,1};
int a[8]={-2,-2,-1,-1,1,1,2,2};//      
int b[8]={1,-1,2,-2,2,-2,1,-1};

void DFS(int x, int y)
{
    if(MAP[x][y] || x<0 || x>n || y<0 || y>m) return ;//  
    if( x == n && y == m )
    {
        cnt ++ ;
        return ;
    }
    MAP[x][y] = 1 ;
    for(int i=0; i<2; i++)
        DFS(x+dx[i],y+dy[i]);
    MAP[x][y] = 0 ;
}


int main()
{
    cin >> n >> m >> mx >> my ;
    memset(MAP,0,sizeof(MAP));
    MAP[mx][my] = 1 ;
    for(int i=0; i<8; i++)
        MAP[mx+a[i]][my+b[i]] = 1 ;
    cnt = 0 ;
    DFS(0,0);
    cout << cnt << endl ;

    return 0;
}

それから、よく考えて、ACにプッシュしました!O(∩∩)Oハハ~

#include 

using namespace std;
int MAP[20][20];
long long cot[20][20];
int n, m, mx, my;
int a[8]= {-2,-2,-1,-1,1,1,2,2}; //      
int b[8]= {1,-1,2,-2,2,-2,1,-1};


int main()
{
    while(cin >> n >> m >> mx >> my )
    {
        for(int i=0;i<20;i++)
            for(int j=0;j<20;j++)
            {
                MAP[i][j]=1;//      ，  1，   
                cot[i][j]=0;//  
            }

        MAP[mx][my] = 0 ;//     
        for(int i=0; i<8; i++)
        {
            int x = mx + a[i] ;
            int y = my + b[i] ;
            if( x >=0 && x<20 && y>=0 && y<20)
                MAP[x][y] = 0 ;
        }
        bool flag = true ;
        for(int i=0; i<20; i++)
        {
            if( flag )
            {
                if(MAP[0][i]==0) flag = false ;
                else cot[0][i] = 1 ;
            }
        }
        flag = true ;
        for(int i=0; i<20; i++)
        {
            if( flag )
            {
                if(MAP[i][0]==0) flag = false ;
                else cot[i][0] = 1 ;
            }
        }

        for(int i=1; i<20; i++)
            for(int j=1; j<20; j++)
                if(MAP[i][j])
                    cot[i][j] = cot[i-1][j]*MAP[i-1][j]+cot[i][j-1]*MAP[i][j-1];

        cout << cot[n][m] << endl ;
    }

    return 0;
}

 
転載先:https://www.cnblogs.com/Asimple/p/5516312.html