再帰練習を繰り返す
33148 ワード
テーマは簡単です.
説明:
碁盤のA点には川を渡る卒がいて、目標のB点まで歩く必要があります.歩行のルール:下へ、または右へ.同時に碁盤上のC点には相手の馬があり、その馬がいる点とジャンプして一歩で達する点を相手の馬の制御点と呼ぶ.そのため「馬が川を渡る卒」と呼ばれている.碁盤は座標で表され、A点(0,0)、B点(n,m)(n,mは15を超えない整数)であり、同じ馬の位置座標が与えられる必要がある.今、卒がA点からB点に到達できる経路の条数を計算し、馬の位置が固定されていると仮定し、卒走一歩馬が一歩歩くわけではない.
入力:
1行に4つのデータをスペースで区切って、B点の座標と馬の座標をそれぞれ表します.
出力:
すべてのパス・バー数を表すデータ.
サンプル:
Sample Input
Sample Output
問題の意味がよくわかりますが、出力ルートの本数です.
問題解決の考え方:
点を2次元配列でリストし、すべてを1に割り当て、馬の制御点をゼロにし、プッシュすることで線路の本数を見つけます.0に遭遇した場合は、現在の回線を終了します.
添付コード:
この問題はまだ少し難しいので、通過できない点をすべて0にする必要があります.もし1つの数の左と上が0であれば、この点も0になります.この点は私がこの問題のために、長い間遅れていたことを考えなければなりません.
説明:
碁盤のA点には川を渡る卒がいて、目標のB点まで歩く必要があります.歩行のルール:下へ、または右へ.同時に碁盤上のC点には相手の馬があり、その馬がいる点とジャンプして一歩で達する点を相手の馬の制御点と呼ぶ.そのため「馬が川を渡る卒」と呼ばれている.碁盤は座標で表され、A点(0,0)、B点(n,m)(n,mは15を超えない整数)であり、同じ馬の位置座標が与えられる必要がある.今、卒がA点からB点に到達できる経路の条数を計算し、馬の位置が固定されていると仮定し、卒走一歩馬が一歩歩くわけではない.
入力:
1行に4つのデータをスペースで区切って、B点の座標と馬の座標をそれぞれ表します.
出力:
すべてのパス・バー数を表すデータ.
サンプル:
Sample Input
6 6 3 3
Sample Output
6
問題の意味がよくわかりますが、出力ルートの本数です.
問題解決の考え方:
点を2次元配列でリストし、すべてを1に割り当て、馬の制御点をゼロにし、プッシュすることで線路の本数を見つけます.0に遭遇した場合は、現在の回線を終了します.
添付コード:
#include
using namespace std;
int main()
{
int n,m,x,y,i,j,k;
while(cin>>n>>m>>x>>y)
{
n=n+5;
m=m+5;
x=x+2;
y=y+2;
int a[n][m];
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
a[i][j]=0;
}
}
for(i=2;i<n-2;i++)
{
for(j=2;j<m-2;j++)
{
a[i][j]=1;
}
}
a[x][y]=0;
a[x+1][y-2]=0;
a[x+2][y-1]=0;
a[x-1][y-2]=0;
a[x-2][y-1]=0;
a[x+1][y+2]=0;
a[x+2][y+1]=0;
a[x-1][y+2]=0;
a[x-2][y+1]=0;
for(i=2;i<n-2;i++)
{
if(a[i][2]==0)
{
for(k=i;k<n-2;k++)
{
a[k][2]=0;
}
}
for(j=2;j<m-2;j++)
{
if(a[n-3][m-3]==0)
break;
if(a[3][2]==0&&a[2][3]==0)
{
a[n-3][m-3]=0;
break;
}
if(a[2][j]==0)
{
for(k=j;k<m-2;k++)
{
a[2][k]=0;
}
}
if(a[i][j]==0)
{
continue;
}
if(a[i-1][j]==0&&a[i][j-1]==0&&i!=2&&j!=2)
a[i][j]=0;
if(a[i-1][j]!=0&&a[i][j-1]!=0)
{
a[i][j]=a[i-1][j]+a[i][j-1];
}
if(a[i-1][j]!=0&&a[i][j-1]==0)
{
a[i][j]=a[i-1][j];
}
if(a[i-1][j]==0&&a[i][j-1]!=0)
{
a[i][j]=a[i][j-1];
}
}
if(j!=m-2)
break;
}
cout<<a[n-3][m-3]<<endl;
}
return 0;
}
解題感想:この問題はまだ少し難しいので、通過できない点をすべて0にする必要があります.もし1つの数の左と上が0であれば、この点も0になります.この点は私がこの問題のために、長い間遅れていたことを考えなければなりません.