思路:關鍵在于找到遞推規律.
如果第m次傳遞後娃娃在同僚A手上,那麼在第m-1次傳遞後,娃娃應該在A的左右鄰居手上,第m-2次傳遞後,娃娃應該在A的左右鄰居的鄰居的手上…
如果第一次傳遞時,娃娃在A手上,那傳遞後,娃娃在A的左右鄰居手上,第二次傳遞後,娃娃在A的左右鄰居的鄰居的手上…
#include<bits/stdc++.h>
using namespace std;
int c[50];//記錄準備第i次傳遞時,i-1次傳遞時娃娃在該同僚手上的方法數目
int after[50];//記錄在第i次傳遞後,娃娃在相應同僚手上的方法數目
int changed[50];//記錄準備第i次傳遞時,i-1次傳遞時可以接到娃娃的同僚。隻有可以接到在i-1次傳遞時娃娃的同僚的左右鄰居才可以在第i次接到娃娃
int r[50];//記錄在第i次傳遞時,可以接到娃娃的同僚
int main(){
int n,m;
int dis;
memset(c,0,sizeof(c));
memset(changed,0,sizeof(c));
memset(r,0,sizeof(r));
memset(after,0,sizeof(after));
cin>>n>>m;
//假設初始時候 同僚A在第1個位置
c[2]=1;//第一次傳娃娃時
c[n]=1;
after[2]=1;
after[n]=1;
changed[2]=1;
changed[n]=1;
int j;
for(int i=2;i<=m;i++)//共傳m次
{
for(j=1;j<=n;j++)
{
if(j==1&&(changed[n]||changed[2]))
{
after[j]=0;
if(changed[n]){
after[1]+=c[n];
r[1]=1;
}
if(changed[2]){
after[1]+=c[2];
r[1]=1;
}
}
else if(j==n&&(changed[n-1]||changed[1]))
{
after[n]=0;
if(changed[n-1]){
after[n]+=c[n-1];
r[n]=1;
}
if(changed[1]){
after[n]+=c[1];
r[n]=1;
}
}
else if(changed[j-1]||changed[j+1])
{
after[j]=0;
if(changed[j-1]){
after[j]+=c[j-1];
r[j]=1;
}
if(changed[j+1]){
after[j]+=c[j+1];
r[j]=1;
}
}
}
memset(changed,0,sizeof(changed));
for(int t=1;t<=n;t++)
{
if(r[t]==1)
{
changed[t]=1;
c[t]=after[t];
r[t]=0;
}
}
}
cout<<c[1]<<'\n';
return 0;
}