蒜头君的新游戏-递推

思路：关键在于找到递推规律.

　　如果第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; 
}