zoj3966 Domino Tiling dp
문제풀이: 제한 조건이 너무 강하기 때문에 가장 좋은 방법은 확정적인 우선 가설 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.