UVA 12113 Overlapping Squares

休言女子非英物,夜夜龙泉壁上鸣。这篇文章主要讲述UVA 12113 Overlapping Squares相关的知识,希望能为你提供帮助。
https://vjudge.net/problem/UVA-12113
 
4*4 棋盘上,用6张2*2的纸 能否摆出给定形状
【UVA 12113 Overlapping Squares】 
暴力枚举 每张纸 放在哪儿
 

#include< cstdio> #include< cstring> using namespace std; char End[5][10],start[5][9]; bool ok; bool vis[9]; void judge(char p[5][9]) { for(int i=0; i< 5; i++) for(int j=0; j< 9; j++) if(End[i][j]!=p[i][j]) return; ok=true; }void dfs(int x,char p[5][9]) { if(ok) return; judge(p); if(x==7) return; char tmp[5][9]; int id=0; for(int i=0; i< 3; i++) for(int j=1; j< =5; j+=2,id++) { if(vis[id]) continue; vis[id]=true; memcpy(tmp,p,sizeof(tmp)); tmp[i][j]=tmp[i][j+2]=tmp[i+2][j]=tmp[i+2][j+2]=‘_‘; tmp[i+1][j-1]=tmp[i+2][j-1]=tmp[i+1][j+3]=tmp[i+2][j+3]=‘|‘; tmp[i+1][j]=tmp[i+1][j+1]=tmp[i+1][j+2]=tmp[i+2][j+1]=‘ ‘; dfs(x+1,tmp); if(ok) return; vis[id]=false; } }int main() { int T=0; while(1) { gets(End[0]); if(End[0][0]==‘0‘) return 0; for(int i=1; i< 5; i++) gets(End[i]); ok=false; memset(start,‘ ‘,sizeof(start)); memset(vis,false,sizeof(vis)); dfs(1,start); printf("Case %d: ",++T); puts(ok ? "Yes" : "No"); } }

 

    推荐阅读