川を渡る卒-2-C++
1463 ワード
以前は河卒のDFSの作り方を書いていましたが、いくつかの小さなデータしか渡せず、データが大きくなると爆発するので、河卒の正解を書きました.
タイトルの説明
碁盤のA点には川を渡る卒がいて、目標のB点まで歩く必要があります.歩行のルール:下へ、または右へ.同時に碁盤上のC点には相手の馬があり、その馬がいる点とジャンプして一歩で達する点を相手の馬の制御点と呼ぶ.そのため「馬が川を渡る卒」と呼ばれている.
碁盤は座標で表され、A点(0,0)、B点(n,m)は20を超えない整数であり、同様に馬の位置座標が与えられる必要がある.
今、卒がA点からB点に到達できる経路の数を計算するように要求されます.馬の位置が固定されていると仮定して、卒が一歩歩いて馬が一歩歩いているわけではありません.入出力フォーマット入力フォーマット:
1行の4つのデータで、それぞれB点座標と馬の座標を表します.
出力フォーマット:
すべてのパス・バー数を表すデータ.
入出力サンプル
サンプル#1を入力:
6 6 3 3
出力サンプル#1:
6
タイトルの説明
碁盤のA点には川を渡る卒がいて、目標のB点まで歩く必要があります.歩行のルール:下へ、または右へ.同時に碁盤上のC点には相手の馬があり、その馬がいる点とジャンプして一歩で達する点を相手の馬の制御点と呼ぶ.そのため「馬が川を渡る卒」と呼ばれている.
碁盤は座標で表され、A点(0,0)、B点(n,m)は20を超えない整数であり、同様に馬の位置座標が与えられる必要がある.
今、卒がA点からB点に到達できる経路の数を計算するように要求されます.馬の位置が固定されていると仮定して、卒が一歩歩いて馬が一歩歩いているわけではありません.入出力フォーマット入力フォーマット:
1行の4つのデータで、それぞれB点座標と馬の座標を表します.
出力フォーマット:
すべてのパス・バー数を表すデータ.
入出力サンプル
サンプル#1を入力:
6 6 3 3
出力サンプル#1:
6
#include
using namespace std;
long long a[1000][1000];
int n,m,x,y;
int mp[1000][1000];
int dir[8][2]={{-1,2},{-1,-2},{1,2},{1,-2},{2,-1},{-2,-1},{2,1},{-2,1}};// DFS
int main(){
cin>>n>>m>>x>>y;
for( int i=0;i<8;i++){//
if(dir[i][0]+x>=0&&dir[i][0]+x<=n&&dir[i][1]+y>=0&&dir[i][1]+y<=n)
mp[dir[i][0]+x][dir[i][1]+y]=1;
}
mp[x][y]=1;
for(int i=0;i<=n;i++){
if(mp[0][i]==1){
a[0][i]=0;
break;
}
a[0][i]=1;
}
for(int i=0;i<=n;i++){
if(mp[i][0]==1){
a[i][0]=0;
break;
}
a[i][0]=1;
}
for(int i=0;i<=n;i++)
for(int j=1;j<=m;j++){
if(mp[i][j]==1){
a[i][j]=0;
}else{
a[i][j]=a[i-1][j]+a[i][j-1];
}
}
cout<