zoj3966 Domino Tiling dp

제목 대의: n*m의 바둑판을 주면 1x2의 칸으로만 조립할 수 있고 4개의 다른 칸의 뿔이 동시에 한 곳에 모일 수 없다.200조 정도의 입력과 출력 임의의 방안.
문제풀이: 제한 조건이 너무 강하기 때문에 가장 좋은 방법은 확정적인 우선 가설 n
#include 
using namespace std;
#define orz printf("orz
"); #define pf printf #define ss system("pause"); #define pii pair #define mp make_pair #define sz size() #define pb push_back #define ft first #define sd second int vis[110][110]; int flag,n,m,ff,cnt; int a[10]; int dx[2][4]={1,0,-1,0,0,1,0,-1}; int dy[2][4]={0,1,0,-1,1,0,-1,0}; int lim1,lim2; void dfs(int x,int y,int kind,int dir,int f) { vis[x][y]=cnt; int xx;int yy; for(int i=0;i<4;i++) { xx=x+dx[kind][dir]; yy=y+dy[kind][dir]; if(xx<1||xx>n||yylim2||vis[xx][yy]) { dir=(dir+1)%4; } else { break; } } if(xx<1||xx>n||yylim2) { return; } if(vis[xx][yy]) { return; } if(f==1) { dfs(xx,yy,kind,dir,f^1); } else { cnt++; dfs(xx,yy,kind,dir,f^1); } } int dp[210][2]; vectored[2],st[2]; int labst[10],labed[10]; void solve() { memset(dp,-1,sizeof(dp)); dp[0][0]=dp[0][1]=0; for(int i=0;i<2;i++) ed[i].clear(); for(int i=0;i<2;i++) st[i].clear(); if(n%2==0) { ed[0].pb( mp(1 ,1 ) ); labed[1]=0; ed[0].pb( mp(2 ,n-1) ); labed[2]=0; ed[0].pb( mp(5 ,n ) ); labed[5]=0; ed[0].pb( mp(6 ,n+1) ); labed[6]=0; ed[1].pb( mp(3 ,n-1) ); labed[3]=1; ed[1].pb( mp(4 ,n ) ); labed[4]=1; ed[1].pb( mp(7 ,n+1) ); labed[7]=1; if(n>2) { ed[1].pb( mp(8 ,n-2)); labed[8]=1; st[1].pb( mp(8 ,n-2)); labst[8]=1; } st[0].pb( mp(1 ,1 ) ); labst[1]=0; st[0].pb( mp(3 ,n-1) ); labst[3]=0; st[0].pb( mp(5 ,n ) ); labst[5]=0; st[0].pb( mp(7 ,n+1) ); labst[7]=0; st[1].pb( mp(2 ,n-1) ); labst[2]=1; st[1].pb( mp(4 ,n ) ); labst[4]=1; st[1].pb( mp(6 ,n+1) ); labst[6]=1; } else { ed[1].pb( mp(1 ,n-1) ); labed[1]=1; ed[1].pb( mp(3 ,n+1) ); labed[3]=1; ed[0].pb( mp(2 ,n-1) ); labed[2]=0; ed[0].pb( mp(4 ,n+1) ); labed[4]=0; st[1].pb( mp(1 ,n-1) ); labst[1]=1; st[1].pb( mp(3 ,n+1) ); labst[3]=1; st[0].pb( mp(2 ,n-1) ); labst[2]=0; st[0].pb( mp(4 ,n+1) ); labst[4]=0; } int t1,len; for(int i=0;im) continue; t1=st[0][j].ft; len=st[0][j].sd; dp[i+len][labed[t1]]=(i<<1)|1; } } if(dp[i][0]!=-1) { for(int j=0;jm) continue; t1=st[1][j].ft; len=st[1][j].sd; dp[i+len][labed[t1]]=(i<<1)|0; } } } } void path(int y,int kind) { //printf("path: %d %d
",y,kind); if(y<1) return; cnt++; int last=dp[y][kind]>>1; int situ=dp[y][kind]&1; lim1=last+1;lim2=y; dfs(1,last+1,situ^1,0,1); path(last,situ); } void toput() { if(ff) { //printf("*******************
"); for(int i=1;i<=m;i++) { for(int j=1;jm) swap(n,m),ff=1; if((n*m) &1) { printf("Impossible!
"); continue; } if(n==1) { lim1=1;lim2=m; cnt++; dfs(1,1,1,0,1); toput(); continue; } solve(); if(dp[m][1]==-1 &&dp[m][0]==-1) { printf("Impossible!
"); } else print(); } return 0; }

좋은 웹페이지 즐겨찾기