UVa 519 Puzzle (II)

题目描述题目要求判断给定的拼图块能否拼成n×mn \times mn×m的矩形。每个拼图块是一个3×43 \times 43×4的矩形每条边的中间可能有一个凸起O\texttt{O}O、一个凹槽I\texttt{I}I或平坦F\texttt{F}F。两块拼图相邻时凸起必须与凹槽匹配。矩形边缘的边必须是平坦的。拼图块不能旋转只能按给定方向使用。输入格式输入包含多个数据块。每个数据块的第一行包含两个整数nnn和mmm0n,m≤60 n, m \le 60n,m≤6表示矩形的行数和列数。接下来n×mn \times mn×m行每行一个长度为444的字符串表示一个拼图块的顶部、右侧、底部、左侧的形状F、O、I。每个数据块后有一个空行。输入以0 0结束。输出格式对于每个数据块输出一行YES或NO表示是否能拼成矩形。样例输入3 5 FOOF FOOI FOOI FOOI FOOF FOOI FOOI FOOI FOOI FOOF FOOI FOOI FOOI FOOF FOOF 0 0输出YES题目分析本题的核心是判断拼图块能否填充矩形满足邻接匹配和边缘平坦条件。必要条件在开始搜索前可以先进行一些必要条件检查四个角上的拼图块必须有两个相邻的平坦边。边缘上的拼图块必须有一条平坦边顶部边缘的顶部为F底部边缘的底部为F左边缘的左侧为F右边缘的右侧为F。内部拼图块不能有平坦边所有边必须是O或I。凸起和凹槽的总数必须匹配整个矩形中水平方向相邻的边中凸起总数应等于凹槽总数垂直方向同理。搜索策略由于n,m≤6n, m \le 6n,m≤6最多363636个拼图块直接回溯搜索是可行的。使用回溯法填充网格按行优先顺序放置拼图块。每次放置时检查与上方和左方已放置块的匹配情况以及是否在边缘时边为平坦。优化将拼图块按特征哈希值排序相同哈希值的块可视为等价避免重复搜索。使用used数组标记已使用的拼图块。复杂度分析最坏情况下36!36!36!不可能但剪枝条件匹配约束、边缘条件大幅缩小搜索空间实际可接受。代码实现// Puzzle (II)// UVa ID: 519// Verdict: Accepted// Submission Date: 2017-05-01// UVa Run Time: 0.160s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structpiece{inttop,right,bottom,left,hash;voidgetSide(stringdescription){topdescription[0]O?1:(description[0]I?2:0);rightdescription[1]O?1:(description[1]I?2:0);bottomdescription[2]O?1:(description[2]I?2:0);leftdescription[3]O?1:(description[3]I?2:0);hashtop*1000right*100bottom*10left;}// more similar, more closer.booloperator(constpiecex)const{returnhashx.hash;}};piece pieces[40];intgrid[10][10],used[40],n,m,t;string description;boolsuccessfulfalse;boolcheck(){inttopLeftFlat0,topRightFlat0,bottomLeftFlat0,bottomRightFlat0;inttopFlat0,rightFlat0,bottomFlat0,leftFlat0,noneFlat0;for(inti0;it;i){if(pieces[i].top0pieces[i].left0)topLeftFlat;if(pieces[i].top0pieces[i].right0)topRightFlat;if(pieces[i].bottom0pieces[i].left0)bottomLeftFlat;if(pieces[i].bottom0pieces[i].right0)bottomRightFlat;if(pieces[i].top0)topFlat;if(pieces[i].right0)rightFlat;if(pieces[i].bottom0)bottomFlat;if(pieces[i].left0)leftFlat;if(pieces[i].top!0pieces[i].right!0pieces[i].bottom!0pieces[i].left!0)noneFlat;}if(topLeftFlat!1||topRightFlat!1||bottomLeftFlat!1||bottomRightFlat!1)returnfalse;if(topFlat!m||bottomFlat!m)returnfalse;if(leftFlat!n||rightFlat!n)returnfalse;if(n2m2noneFlat!(n-2)*(m-2))returnfalse;returntrue;}boolvalidate(inti,intj,intk){if(i0pieces[k].top!0)returnfalse;if(i(n-1)pieces[k].bottom!0)returnfalse;if(j0pieces[k].left!0)returnfalse;if(j(m-1)pieces[k].right!0)returnfalse;if(i0(pieces[k].toppieces[grid[i-1][j]].bottom)!3)returnfalse;if(j0(pieces[k].leftpieces[grid[i][j-1]].right)!3)returnfalse;returntrue;}voidbacktrack(inti,intj){if(in)successfultrue;else{for(intk0;kt;k)if(!used[k](k0||used[k-1]||pieces[k].hash!pieces[k-1].hash)validate(i,j,k)){used[k]1;grid[i][j]k;if(j1m)backtrack(i1,0);elsebacktrack(i,j1);if(successful)return;used[k]0;}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);while(cinnm,n0){tn*m;for(inti0;it;i){cindescription;pieces[i].getSide(description);}successfulfalse;if(check()){sort(pieces,piecest);memset(used,0,sizeof(used));backtrack(0,0);}cout(successful?YES:NO)\n;}return0;}