UVa 387 A Puzzling Problem

题目描述本题的目标是编写一个程序接受111到555个拼图片如下所示并尝试将它们拼成一个4×44 \times 44×4的正方形。拼图片不能旋转或翻转必须全部使用。可能有多个解任意一个均可。输入格式输入文件包含多个拼图即多个拼图片集合。第一行是第一个拼图中拼图片的数量。每个拼片由一行两个整数行数和列数和后续若干行指定形状。形状由0和1字符组成1表示拼片的实体部分。例如拼片 A 的表示如下2 3 111 101拼片按输入顺序编号#1、#2 等。所有拼片不超过444行444列。输入以拼图片数量为000结束。输出格式输出一个4×44 \times 44×4的正方形每个位置用拼片编号填充。不同拼图的解之间用一个空行分隔。如果无解输出No solution possible。样例输入4 2 3 111 101 4 2 01 01 11 01 2 1 1 1 3 2 10 10 11 4 1 4 1111 1 4 1111 1 4 1111 2 3 111 001 5 2 2 11 11 2 3 111 100 3 2 11 01 01 1 3 111 1 1 0样例输出1112 1412 3422 3442 No solution possible 1133 1153 2223 2444题目分析问题的本质这是一个精确覆盖问题exact cover\texttt{exact cover}exact cover类似于拼图游戏。需要将nnn个拼片1≤n≤51 \leq n \leq 51≤n≤5放入4×44 \times 44×4的网格中每个拼片的实体部分占据111个或多个格子所有拼片必须恰好覆盖全部161616个格子且不能重叠。关键约束拼片不能旋转或翻转所有拼片的实体格子总数必须恰好为161616拼片可以放置在网格的任何位置只要不超出边界拼片的0部分不占格子只用于定义形状搜索策略使用深度优先搜索DFS\texttt{DFS}DFS按顺序放置拼片。对于每个拼片尝试所有可能的位置左上角坐标检查是否与已放置的拼片重叠。如果成功放置递归处理下一个拼片。参考代码// A Puzzling Problem// UVa ID: 387// Verdict: Accepted// Submission Date: 2016-07-05// UVa Run Time: 0.170s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorpairpairint,int,vectorintpieces;// 拼片((行数,列数), 形状矩阵)vectorboolvisited;// 拼片是否已使用intgrid[4][4];// 网格// 输出当前网格voiddisplay(){for(inti0;i4;i){for(intj0;j4;j)coutgrid[i][j];coutendl;}}// 从网格中移除指定编号的拼片voidpullOut(intdigit){for(inti0;i4;i)for(intj0;j4;j)if(grid[i][j](digit1))grid[i][j]0;}// 将拼片放入网格的指定位置boolpushIn(intdigit,introw,intcolumn){// 检查是否超出边界if(rowpieces[digit].first.first4||columnpieces[digit].first.second4)returnfalse;boolsuccesstrue;// 尝试放置for(intr0;rpieces[digit].first.first;r)for(intc0;cpieces[digit].first.second;c){intblockpieces[digit].second[r*pieces[digit].first.secondc];if(grid[rowr][columnc]0)grid[rowr][columnc]block;elseif(block!0)// 重叠{successfalse;gotoout;}}out:if(!success)pullOut(digit);returnsuccess;}// 深度优先搜索booldfs(intdepth,intn){if(depthn)// 所有拼片都放置成功{display();returntrue;}for(inti0;ivisited.size();i)if(!visited[i]){visited[i]true;for(introw0;row4;row)for(intcolumn0;column4;column)if((grid[row][column]0||pieces[i].second.front()0)pushIn(i,row,column)){if(dfs(depth1,n))returntrue;pullOut(i);// 回溯}visited[i]false;}returnfalse;}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn,cases0,row,column;string line;while(cinn,n){pieces.clear();intcell0;// 实体格子总数// 读取拼片for(inti1;in;i){cinrowcolumn;vectorintmatrix;for(intj1;jrow;j){cinline;cellcount(line.begin(),line.end(),1);for(charc:line)matrix.push_back(c1?i:0);}pieces.push_back(make_pair(make_pair(row,column),matrix));}// 测试用例间空行if(cases)coutendl;// 快速检查所有拼片的实体格子总数必须为 16if(cell!16){coutNo solution possibleendl;continue;}visited.resize(n);fill(visited.begin(),visited.end(),false);memset(grid,0,sizeof(grid));if(!dfs(0,n))coutNo solution possibleendl;}return0;}