爸爸 妈妈 猎人和狗 有两男孩 两个女孩 。他们要过河，但猎人不在的时候，狗咬任何人，当爸爸不在的时候，妈妈打小男孩，妈妈不在的时候，爸爸打小女孩，他们怎么过去

爸爸 妈妈 猎人和狗 有两男孩 两个女孩 。他们要过河，但猎人不在的时候，狗咬任何人，当爸爸不在的时候，妈妈打小男孩，妈妈不在的时候，爸爸打小女孩，他们怎么过去

有一天看到的一个网上题目，一时兴起便写了一下，o(^▽^)o

#include<stdio.h>#define N 10// 爸 妈 猎人 狼 两个儿子 两个女儿int dp[2][1<<N];
int path[2][1<<N];
int vis[2][1<<N];int ok(int cur)
{if((cur&(1<<0))&&((cur&(1<<6))||(cur&(1<<7)))&&!(cur&(1<<1))) return 0;if((cur&(1<<1))&&((cur&(1<<4))||(cur&(1<<5)))&&!(cur&(1<<0))) return 0;if((cur&(1<<3))&&!(cur&(1<<2))&&(cur^(1<<3))) return 0;return 1;
}int get_num(int x)
{int ans=0;while(x){ans++;x&=(x-1);}return ans;
}void print(int cur)
{if(cur&(1<<0)) printf("爸爸 ");if(cur&(1<<1)) printf("妈妈 ");if(cur&(1<<2)) printf("猎人 ");if(cur&(1<<3)) printf("狼 ");if(cur&(1<<4)) printf("儿子1 ");if(cur&(1<<5)) printf("儿子2 ");if(cur&(1<<6)) printf("女儿1 ");if(cur&(1<<7)) printf("女儿2 ");printf("\n");}void show(int side,int cur)
{int i,j;if((cur&path[side][cur])==0) return ;int all=(1<<8)-1;show(side^1,path[side][cur]);if(side) printf("去: ");else printf("来: ");print(cur&path[side][cur]);
}int dfs(int side,int cur)
{if(vis[side][cur]) return 0;vis[side][cur]=1;int all=(1<<8)-1;if(side==1&&cur==all) return 1;if(dp[side][cur]!=-1) return dp[side][cur];for(int to=1;to<=all;to++){if((cur&to)!=to) continue;int num=get_num(to);if(num>2) continue;if(!(to&(1<<0))&&!(to&(1<<1))&&!(to&(1<<2))) continue;if(!ok(to)) continue;if(!ok(cur^to)) continue;if(!ok(all^(cur^to))) continue;if(dfs(side^1,all^(cur^to))){path[side^1][all^cur^to]=cur;return dp[side][cur]=1;}}return dp[side][cur]=0;
}int main()
{int i,j;for(i=0;i<(1<<N);i++) dp[0][i]=dp[1][i]=-1;for(i=0;i<(1<<N);i++){vis[0][i]=vis[1][i]=0;path[0][i]=path[1][i]=0;}printf("%d\n",dfs(0,(1<<8)-1));show(1,(1<<8)-1);return 0;
}