题意:给了一个矩阵图，要求使用回路把图中的树全部吃掉的方案树，没有树的点不能走，吃完了这个点也就没有了，走到哪吃到哪
用插头dp搞
#include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <string.h> using namespace std; typedef long long LL; int G[11][11]; int nrows,ncols; struct State { int up[11]; int left; int encode()const { int key=left; for(int i=0; i<ncols; i++)key=key*2+up[i]; return key; } bool next(int row,int col, int U, int D, int L, int R,State &T)const { if(row==nrows-1 && D!=0 )return false; if(col==ncols-1 && R!=0 )return false; int must_left = (col>0&&left!=0); int must_up = (row>0 && up[col]!=0); if( ( must_left!=0 && L==0) || (must_left==0 && L!=0) )return false ; if( ( must_up !=0 && U== 0) || (must_up ==0 && U!=0 )) return false; for(int i=0; i<ncols; i++)T.up[i]=up[i]; T.up[col]=D; T.left=R; return true; } }; LL memo[11][11][1<<13]; LL rec(int row,int col,const State &S) { if(col == ncols ){ col=0; row++ ;} if(row == nrows) return 1; int key=S.encode(); LL &res=memo[row][col][key]; if(res>=0)return res; res=0; State T; if(G[row][col]) { if(S.next(row,col,1,1,0,0,T)) res+=rec(row,col+1,T); if(S.next(row,col,1,0,1,0,T)) res+=rec(row,col+1,T); if(S.next(row,col,1,0,0,1,T)) res+=rec(row,col+1,T); if(S.next(row,col,0,1,1,0,T)) res+=rec(row,col+1,T); if(S.next(row,col,0,1,0,1,T)) res+=rec(row,col+1,T); if(S.next(row,col,0,0,1,1,T)) res+=rec(row,col+1,T); }else { if(S.next(row,col,0,0,0,0,T)) res+=rec(row,col+1,T); } return res; } int main() { int cas; scanf("%d",&cas); for(int cc=1; cc<=cas; cc++) { scanf("%d%d",&nrows,&ncols); for(int i=0; i<nrows; i++) for(int j=0; j<ncols ;j++) scanf("%d",&G[i][j]); State S; memset(&S,0,sizeof(S)); memset(memo,-1,sizeof(memo)); LL ans=rec(0,0,S); printf("Case %d: There are %I64d ways to eat the trees. ",cc,ans); } return 0; }