Vijos 1121 馬攔過河卒，vijos1121攔過河卒

Vijos 1121 馬攔過河卒，vijos1121攔過河卒

首先要看清題目，卒只能向右或者向下走。而不是四周轉。這樣的話就無解了。

定義f[i][j]，表示走到(i,j)這個點時的總步數。這樣就寫出了一個遞推公式f[i][j]=f[i-1]+f[i][j-1]。因為卒是從(0,0)出發，所以f[0][0]=1,因為 f[i][j]只能從前一個狀態轉移過來。所以在轉移前需要加特判即(i-1,j)和(i,j-1)兩點不是馬所控制的點。所以在遞推之前還應有一個預處理。來處理馬所能控制的點，預處理很好寫。剩下的沒有什麼了。輸出目標節點的 f 值即可。

代碼：

#include<iostream>
#include<cstdio>
using namespace std;
int x1,y1,x2,y2;
int f[16][16],a[16][16],ans;
int mx[8]={1,2,2,1,-1,-2,-2,-1};
int my[8]={2,1,-1,-2,-2,-1,1,2};
int main()
{
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    a[x2][y2]=1;
    for(int i=0;i<=7;i++){
      if(x2+mx[i]<=x1&&y2+my[i]<=y1)
      a[x2+mx[i]][y2+my[i]]=1;
    }
    f[0][0]=1;
    for(int i=0;i<=x1;i++)
      for(int j=0;j<=y1;j++){
          if(i>0&&!a[i-1][j])
            f[i][j]+=f[i-1][j];
          if(j>0&&!a[i][j-1])
            f[i][j]+=f[i][j-1];
      }
    printf("%d",f[x1][y1]);
}