)
题目描述
题目要求判断给定的拼图块能否拼成n×mn \times mn×m的矩形。每个拼图块是一个3×43 \times 43×4的矩形，每条边的中间可能有一个凸起（O\texttt{O}O）、一个凹槽（I\texttt{I}I）或平坦（F\texttt{F}F）。两块拼图相邻时，凸起必须与凹槽匹配。矩形边缘的边必须是平坦的。拼图块不能旋转，只能按给定方向使用。
输入格式
输入包含多个数据块。每个数据块的第一行包含两个整数nnn和mmm（0<n,m≤60 < n, m \le 60<n,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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structpiece{inttop,right,bottom,left,hash;voidgetSide(string&description){top=description[0]=='O'?1:(description[0]=='I'?2:0);right=description[1]=='O'?1:(description[1]=='I'?2:0);bottom=description[2]=='O'?1:(description[2]=='I'?2:0);left=description[3]=='O'?1:(description[3]=='I'?2:0);hash=top*1000+right*100+bottom*10+left;}// more similar, more closer.booloperator<(constpiece&x)const{returnhash<x.hash;}};piece pieces[40];intgrid[10][10],used[40],n,m,t;string description;boolsuccessful=false;boolcheck(){inttopLeftFlat=0,topRightFlat=0,bottomLeftFlat=0,bottomRightFlat=0;inttopFlat=0,rightFlat=0,bottomFlat=0,leftFlat=0,noneFlat=0;for(inti=0;i<t;i++){if(pieces[i].top==0&&pieces[i].left==0)topLeftFlat++;if(pieces[i].top==0&&pieces[i].right==0)topRightFlat++;if(pieces[i].bottom==0&&pieces[i].left==0)bottomLeftFlat++;if(pieces[i].bottom==0&&pieces[i].right==0)bottomRightFlat++;if(pieces[i].top==0)topFlat++;if(pieces[i].right==0)rightFlat++;if(pieces[i].bottom==0)bottomFlat++;if(pieces[i].left==0)leftFlat++;if(pieces[i].top!=0&&pieces[i].right!=0&&pieces[i].bottom!=0&&pieces[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(n>=2&&m>=2&&noneFlat!=(n-2)*(m-2))returnfalse;returntrue;}boolvalidate(inti,intj,intk){if(i==0&&pieces[k].top!=0)returnfalse;if(i==(n-1)&&pieces[k].bottom!=0)returnfalse;if(j==0&&pieces[k].left!=0)returnfalse;if(j==(m-1)&&pieces[k].right!=0)returnfalse;if(i>0&&(pieces[k].top+pieces[grid[i-1][j]].bottom)!=3)returnfalse;if(j>0&&(pieces[k].left+pieces[grid[i][j-1]].right)!=3)returnfalse;returntrue;}voidbacktrack(inti,intj){if(i==n)successful=true;else{for(intk=0;k<t;k++)if(!used[k]&&(k==0||used[k-1]||pieces[k].hash!=pieces[k-1].hash)&&validate(i,j,k)){used[k]=1;grid[i][j]=k;if(j+1==m)backtrack(i+1,0);elsebacktrack(i,j+1);if(successful)return;used[k]=0;}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);while(cin>>n>>m,n>0){t=n*m;for(inti=0;i<t;i++){cin>>description;pieces[i].getSide(description);}successful=false;if(check()){sort(pieces,pieces+t);memset(used,0,sizeof(used));backtrack(0,0);}cout<<(successful?"YES":"NO")<<'\n';}return0;}
