怎么删除网站里的死链接,psd网站首页图片,企业管理软件属于系统软件吗,开网站做彩票赚钱吗P4205 [NOI2005]智慧珠游戏 题意 题目描述 智慧珠游戏拼盘由一个三角形盘件和\(12\)个形态各异的零件组成。拼盘的盘 件如图\(1\)所示 对于由珠子构成的零件#xff0c;可以放到盘件的任一位置#xff0c;条件是能有地方放#xff0c;且尺寸合适#xff0c;所有的零件都允许…P4205 [NOI2005]智慧珠游戏 题意 题目描述 智慧珠游戏拼盘由一个三角形盘件和\(12\)个形态各异的零件组成。拼盘的盘 件如图\(1\)所示 对于由珠子构成的零件可以放到盘件的任一位置条件是能有地方放且尺寸合适所有的零件都允许旋转(\(0º,90º,180º,270º\))和翻转(水平、竖直)。 现给出一个盘件的初始布局求一种可行的智慧珠摆放方案使所有的零件都能放进盘件中。 输入输出格式 输入格式 文件中包含初始的盘件描述一共有\(10\)行第\(i\)行有\(i\)个字符。如果第\(i\)行的第\(j\)个字符是字母“\(A\)”至“\(L\)”中的一个则表示第\(i\)行第\(j\)列的格子上已经放了零件零件的编号为对应的字母。如果第\(i\)行的第\(j\)个字符是“.”则表示第\(i\)行第\(j\)列的格子上没有放零件。输入保证预放的零件已摆放在盘件中。 输出格式 如果能找到解向输出文件打印\(10\)行为放完全部\(12\)个零件后的布局。其中第\(i\)行应包含\(i\)个字符第\(i\)行的第\(j\)个字符表示第\(i\)行第\(j\)列的格子上放的是哪个零件。如果无解输出单独的一个字符串‘No solution’(不要引号请注意大小写)。所有的数据保证最多只有一组解。 输入输出样例 输入样例 .
..
...
....
.....
.....C
...CCC.
EEEHH...
E.HHH....
E......... 输出样例 B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF 思路 其他三道题都没做这道题\(AC\)了不也不错吗 --Mercury 搜索模拟测试考黑题简直毒瘤。考场上用了两个多小时敲这道题还差一个小剪枝才能\(AC\)。 首先我们枚举每一种零件的放置方法然后暴力枚举逐个判断每个位置上应该放哪个零件。为了提高枚举效率我们规定放入的零件对上一行没有影响也就是说我们枚举每个位置放置的零件也就是枚举该零件的左上角放置在该位置时是否有可行方案。 然而最后被这样的一组数据卡掉了 .
..
...
....
.....
......
.......
.......J
......JJJ
.......J.. 显然右下角什么都放不进去而我的搜索是顺序搜索所以一直要到快搜索完才会判断到右下角我的程序也因此被卡到了\(8\)秒 明明\(DLX\)才是正解好吧神tm暴搜被卡 。于是有这样的一个优化对于当前局面如果最小联通块的大小\(\leq 2\)那么就是不可行的方案直接回溯。这样就可以很快地跑完了。 AC代码 #includebits/stdc.h
using namespace std;
char G[15][15];
bool vis[26],hjj[15][15];
inline char readc()
{char chgetchar();while(ch!.!isalpha(ch)) chgetchar();return ch;
}
inline void print()
{for(int i1;i10;i){for(int j1;ji;j) putchar(G[i][j]);putchar(\n);}
}
bool judge(int x,int y,char z,int w)
{if(zA){if(w0G[x][y].G[x][y1].G[x1][y].) return true;else if(w1G[x][y].G[x][y1].G[x1][y1].) return true;else if(w2G[x][y].G[x1][y].G[x1][y-1].) return true;else if(w3G[x][y].G[x1][y].G[x1][y1].) return true;return false;}else if(zB){if(w0G[x][y].G[x][y1].G[x][y2].G[x][y3].) return true;else if(w1G[x][y].G[x1][y].G[x2][y].G[x3][y].) return true;return false;}else if(zC){if(w0G[x][y].G[x][y1].G[x][y2].G[x1][y].) return true;else if(w1G[x][y].G[x][y1].G[x1][y1].G[x2][y1].) return true;else if(w2G[x][y].G[x1][y].G[x1][y-1].G[x1][y-2].) return true;else if(w3G[x][y].G[x1][y].G[x2][y].G[x2][y1].) return true;else if(w4G[x][y].G[x1][y].G[x1][y1].G[x1][y2].) return true;else if(w5G[x][y].G[x][y1].G[x][y2].G[x1][y2].) return true;else if(w6G[x][y].G[x][y1].G[x1][y].G[x2][y].) return true;else if(w7G[x][y].G[x1][y].G[x2][y].G[x2][y-1].) return true;return false;}else if(zD){if(w0G[x][y].G[x][y1].G[x1][y].G[x1][y1].) return true;return false;}else if(zE){if(w0G[x][y].G[x1][y].G[x2][y].G[x2][y1].G[x2][y2].) return true;else if(w1G[x][y].G[x][y1].G[x][y2].G[x1][y].G[x2][y].) return true;else if(w2G[x][y].G[x][y1].G[x][y2].G[x1][y2].G[x2][y2].) return true;else if(w3G[x][y].G[x1][y].G[x2][y].G[x2][y-1].G[x2][y-2].) return true;return false;}else if(zF){if(w0G[x][y].G[x][y1].G[x][y2].G[x][y3].G[x1][y1].) return true;else if(w1G[x][y].G[x1][y].G[x2][y].G[x3][y].G[x1][y-1].) return true;else if(w2G[x][y].G[x1][y].G[x1][y1].G[x1][y-1].G[x1][y-2].) return true;else if(w3G[x][y].G[x1][y].G[x2][y].G[x2][y1].G[x3][y].) return true;else if(w4G[x][y].G[x1][y].G[x1][y-1].G[x1][y1].G[x1][y2].) return true;else if(w5G[x][y].G[x][y1].G[x][y2].G[x][y3].G[x1][y2].) return true;else if(w6G[x][y].G[x1][y].G[x1][y1].G[x2][y].G[x3][y].) return true;else if(w7G[x][y].G[x1][y].G[x2][y].G[x2][y-1].G[x3][y].) return true;return false;}else if(zG){if(w0G[x][y].G[x][y1].G[x][y2].G[x1][y].G[x1][y2].) return true;else if(w1G[x][y].G[x][y1].G[x1][y1].G[x2][y].G[x2][y1].) return true;else if(w2G[x][y].G[x][y2].G[x1][y].G[x1][y1].G[x1][y2].) return true;else if(w3G[x][y].G[x][y1].G[x1][y].G[x2][y].G[x2][y1].) return true;return false;}else if(zH){if(w0G[x][y].G[x][y1].G[x][y2].G[x1][y].G[x1][y1].) return true;else if(w1G[x][y].G[x][y1].G[x1][y].G[x1][y1].G[x2][y1].) return true;else if(w2G[x][y].G[x][y1].G[x1][y].G[x1][y-1].G[x1][y1].) return true;else if(w3G[x][y].G[x1][y].G[x1][y1].G[x2][y].G[x2][y1].) return true;else if(w4G[x][y].G[x][y1].G[x1][y].G[x1][y1].G[x1][y2].) return true;else if(w5G[x][y].G[x][y1].G[x1][y].G[x1][y1].G[x2][y].) return true;else if(w6G[x][y].G[x][y1].G[x][y2].G[x1][y1].G[x1][y2].) return true;else if(w7G[x][y].G[x1][y].G[x1][y-1].G[x2][y].G[x2][y-1].) return true;return false;}else if(zI){if(w0G[x][y].G[x][y1].G[x][y2].G[x1][y2].G[x1][y3].) return true;else if(w1G[x][y].G[x1][y].G[x2][y].G[x2][y-1].G[x3][y-1].) return true;else if(w2G[x][y].G[x][y1].G[x1][y1].G[x1][y2].G[x1][y3].) return true;else if(w3G[x][y].G[x1][y].G[x1][y-1].G[x2][y-1].G[x3][y-1].) return true;else if(w4G[x][y].G[x][y1].G[x][y2].G[x1][y].G[x1][y-1].) return true;else if(w5G[x][y].G[x1][y].G[x2][y].G[x2][y1].G[x3][y1].) return true;else if(w6G[x][y].G[x][y1].G[x1][y].G[x1][y-1].G[x1][y-2].) return true;else if(w7G[x][y].G[x1][y].G[x1][y1].G[x2][y1].G[x3][y1].) return true;return false;}else if(zJ){if(w0G[x][y].G[x1][y].G[x1][y-1].G[x1][y1].G[x2][y].) return true;return false;}else if(zK){if(w0G[x][y].G[x1][y].G[x1][y1].G[x2][y1].G[x2][y2].) return true;else if(w1G[x][y].G[x][y1].G[x1][y].G[x1][y-1].G[x2][y-1].) return true;else if(w2G[x][y].G[x][y1].G[x1][y1].G[x1][y2].G[x2][y2].) return true;else if(w3G[x][y].G[x1][y].G[x1][y-1].G[x2][y-1].G[x2][y-2].) return true;return false;}else if(zL){if(w0G[x][y].G[x][y1].G[x][y2].G[x][y3].G[x1][y].) return true;else if(w1G[x][y].G[x][y1].G[x1][y1].G[x2][y1].G[x3][y1].) return true;else if(w2G[x][y].G[x1][y].G[x1][y-1].G[x1][y-2].G[x1][y-3].) return true;else if(w3G[x][y].G[x1][y].G[x2][y].G[x3][y].G[x3][y1].) return true;else if(w4G[x][y].G[x1][y].G[x1][y1].G[x1][y2].G[x1][y3].) return true;else if(w5G[x][y].G[x][y1].G[x1][y].G[x2][y].G[x3][y].) return true;else if(w6G[x][y].G[x][y1].G[x][y2].G[x][y3].G[x1][y3].) return true;else if(w7G[x][y].G[x1][y].G[x2][y].G[x3][y].G[x3][y-1].) return true;return false;}return false;
}
void fill(int x,int y,char z,int w)
{if(zA){if(w0) G[x][y]G[x][y1]G[x1][y]A;else if(w1) G[x][y]G[x][y1]G[x1][y1]A;else if(w2) G[x][y]G[x1][y]G[x1][y-1]A;else if(w3) G[x][y]G[x1][y]G[x1][y1]A;}else if(zB){if(w0) G[x][y]G[x][y1]G[x][y2]G[x][y3]B;else if(w1) G[x][y]G[x1][y]G[x2][y]G[x3][y]B;}else if(zC){if(w0) G[x][y]G[x][y1]G[x][y2]G[x1][y]C;else if(w1) G[x][y]G[x][y1]G[x1][y1]G[x2][y1]C;else if(w2) G[x][y]G[x1][y]G[x1][y-1]G[x1][y-2]C;else if(w3) G[x][y]G[x1][y]G[x2][y]G[x2][y1]C;else if(w4) G[x][y]G[x1][y]G[x1][y1]G[x1][y2]C;else if(w5) G[x][y]G[x][y1]G[x][y2]G[x1][y2]C;else if(w6) G[x][y]G[x][y1]G[x1][y]G[x2][y]C;else if(w7) G[x][y]G[x1][y]G[x2][y]G[x2][y-1]C;}else if(zD) G[x][y]G[x][y1]G[x1][y]G[x1][y1]D;else if(zE){if(w0) G[x][y]G[x1][y]G[x2][y]G[x2][y1]G[x2][y2]E;else if(w1) G[x][y]G[x][y1]G[x][y2]G[x1][y]G[x2][y]E;else if(w2) G[x][y]G[x][y1]G[x][y2]G[x1][y2]G[x2][y2]E;else if(w3) G[x][y]G[x1][y]G[x2][y]G[x2][y-1]G[x2][y-2]E;}else if(zF){if(w0) G[x][y]G[x][y1]G[x][y2]G[x][y3]G[x1][y1]F;else if(w1) G[x][y]G[x1][y]G[x2][y]G[x3][y]G[x1][y-1]F;else if(w2) G[x][y]G[x1][y]G[x1][y1]G[x1][y-1]G[x1][y-2]F;else if(w3) G[x][y]G[x1][y]G[x2][y]G[x2][y1]G[x3][y]F;else if(w4) G[x][y]G[x1][y]G[x1][y-1]G[x1][y1]G[x1][y2]F;else if(w5) G[x][y]G[x][y1]G[x][y2]G[x][y3]G[x1][y2]F;else if(w6) G[x][y]G[x1][y]G[x1][y1]G[x2][y]G[x3][y]F;else if(w7) G[x][y]G[x1][y]G[x2][y]G[x2][y-1]G[x3][y]F;}else if(zG){if(w0) G[x][y]G[x][y1]G[x][y2]G[x1][y]G[x1][y2]G;else if(w1) G[x][y]G[x][y1]G[x1][y1]G[x2][y]G[x2][y1]G;else if(w2) G[x][y]G[x][y2]G[x1][y]G[x1][y1]G[x1][y2]G;else if(w3) G[x][y]G[x][y1]G[x1][y]G[x2][y]G[x2][y1]G;}else if(zH){if(w0) G[x][y]G[x][y1]G[x][y2]G[x1][y]G[x1][y1]H;else if(w1) G[x][y]G[x][y1]G[x1][y]G[x1][y1]G[x2][y1]H;else if(w2) G[x][y]G[x][y1]G[x1][y]G[x1][y-1]G[x1][y1]H;else if(w3) G[x][y]G[x1][y]G[x1][y1]G[x2][y]G[x2][y1]H;else if(w4) G[x][y]G[x][y1]G[x1][y]G[x1][y1]G[x1][y2]H;else if(w5) G[x][y]G[x][y1]G[x1][y]G[x1][y1]G[x2][y]H;else if(w6) G[x][y]G[x][y1]G[x][y2]G[x1][y1]G[x1][y2]H;else if(w7) G[x][y]G[x1][y]G[x1][y-1]G[x2][y]G[x2][y-1]H;}else if(zI){if(w0) G[x][y]G[x][y1]G[x][y2]G[x1][y2]G[x1][y3]I;else if(w1) G[x][y]G[x1][y]G[x2][y]G[x2][y-1]G[x3][y-1]I;else if(w2) G[x][y]G[x][y1]G[x1][y1]G[x1][y2]G[x1][y3]I;else if(w3) G[x][y]G[x1][y]G[x1][y-1]G[x2][y-1]G[x3][y-1]I;else if(w4) G[x][y]G[x][y1]G[x][y2]G[x1][y]G[x1][y-1]I;else if(w5) G[x][y]G[x1][y]G[x2][y]G[x2][y1]G[x3][y1]I;else if(w6) G[x][y]G[x][y1]G[x1][y]G[x1][y-1]G[x1][y-2]I;else if(w7) G[x][y]G[x1][y]G[x1][y1]G[x2][y1]G[x3][y1]I;}else if(zJ) G[x][y]G[x1][y]G[x1][y-1]G[x1][y1]G[x2][y]J;else if(zK){if(w0) G[x][y]G[x1][y]G[x1][y1]G[x2][y1]G[x2][y2]K;else if(w1) G[x][y]G[x][y1]G[x1][y]G[x1][y-1]G[x2][y-1]K;else if(w2) G[x][y]G[x][y1]G[x1][y1]G[x1][y2]G[x2][y2]K;else if(w3) G[x][y]G[x1][y]G[x1][y-1]G[x2][y-1]G[x2][y-2]K;}else if(zL){if(w0) G[x][y]G[x][y1]G[x][y2]G[x][y3]G[x1][y]L;else if(w1) G[x][y]G[x][y1]G[x1][y1]G[x2][y1]G[x3][y1]L;else if(w2) G[x][y]G[x1][y]G[x1][y-1]G[x1][y-2]G[x1][y-3]L;else if(w3) G[x][y]G[x1][y]G[x2][y]G[x3][y]G[x3][y1]L;else if(w4) G[x][y]G[x1][y]G[x1][y1]G[x1][y2]G[x1][y3]L;else if(w5) G[x][y]G[x][y1]G[x1][y]G[x2][y]G[x3][y]L;else if(w6) G[x][y]G[x][y1]G[x][y2]G[x][y3]G[x1][y3]L;else if(w7) G[x][y]G[x1][y]G[x2][y]G[x3][y]G[x3][y-1]L;}
}
void unfill(int x,int y,char z,int w)
{if(zA){if(w0) G[x][y]G[x][y1]G[x1][y].;else if(w1) G[x][y]G[x][y1]G[x1][y1].;else if(w2) G[x][y]G[x1][y]G[x1][y-1].;else if(w3) G[x][y]G[x1][y]G[x1][y1].;}else if(zB){if(w0) G[x][y]G[x][y1]G[x][y2]G[x][y3].;else if(w1) G[x][y]G[x1][y]G[x2][y]G[x3][y].;}else if(zC){if(w0) G[x][y]G[x][y1]G[x][y2]G[x1][y].;else if(w1) G[x][y]G[x][y1]G[x1][y1]G[x2][y1].;else if(w2) G[x][y]G[x1][y]G[x1][y-1]G[x1][y-2].;else if(w3) G[x][y]G[x1][y]G[x2][y]G[x2][y1].;else if(w4) G[x][y]G[x1][y]G[x1][y1]G[x1][y2].;else if(w5) G[x][y]G[x][y1]G[x][y2]G[x1][y2].;else if(w6) G[x][y]G[x][y1]G[x1][y]G[x2][y].;else if(w7) G[x][y]G[x1][y]G[x2][y]G[x2][y-1].;}else if(zD) G[x][y]G[x][y1]G[x1][y]G[x1][y1].;else if(zE){if(w0) G[x][y]G[x1][y]G[x2][y]G[x2][y1]G[x2][y2].;else if(w1) G[x][y]G[x][y1]G[x][y2]G[x1][y]G[x2][y].;else if(w2) G[x][y]G[x][y1]G[x][y2]G[x1][y2]G[x2][y2].;else if(w3) G[x][y]G[x1][y]G[x2][y]G[x2][y-1]G[x2][y-2].;}else if(zF){if(w0) G[x][y]G[x][y1]G[x][y2]G[x][y3]G[x1][y1].;else if(w1) G[x][y]G[x1][y]G[x2][y]G[x3][y]G[x1][y-1].;else if(w2) G[x][y]G[x1][y]G[x1][y1]G[x1][y-1]G[x1][y-2].;else if(w3) G[x][y]G[x1][y]G[x2][y]G[x2][y1]G[x3][y].;else if(w4) G[x][y]G[x1][y]G[x1][y-1]G[x1][y1]G[x1][y2].;else if(w5) G[x][y]G[x][y1]G[x][y2]G[x][y3]G[x1][y2].;else if(w6) G[x][y]G[x1][y]G[x1][y1]G[x2][y]G[x3][y].;else if(w7) G[x][y]G[x1][y]G[x2][y]G[x2][y-1]G[x3][y].;}else if(zG){if(w0) G[x][y]G[x][y1]G[x][y2]G[x1][y]G[x1][y2].;else if(w1) G[x][y]G[x][y1]G[x1][y1]G[x2][y]G[x2][y1].;else if(w2) G[x][y]G[x][y2]G[x1][y]G[x1][y1]G[x1][y2].;else if(w3) G[x][y]G[x][y1]G[x1][y]G[x2][y]G[x2][y1].;}else if(zH){if(w0) G[x][y]G[x][y1]G[x][y2]G[x1][y]G[x1][y1].;else if(w1) G[x][y]G[x][y1]G[x1][y]G[x1][y1]G[x2][y1].;else if(w2) G[x][y]G[x][y1]G[x1][y]G[x1][y-1]G[x1][y1].;else if(w3) G[x][y]G[x1][y]G[x1][y1]G[x2][y]G[x2][y1].;else if(w4) G[x][y]G[x][y1]G[x1][y]G[x1][y1]G[x1][y2].;else if(w5) G[x][y]G[x][y1]G[x1][y]G[x1][y1]G[x2][y].;else if(w6) G[x][y]G[x][y1]G[x][y2]G[x1][y1]G[x1][y2].;else if(w7) G[x][y]G[x1][y]G[x1][y-1]G[x2][y]G[x2][y-1].;}else if(zI){if(w0) G[x][y]G[x][y1]G[x][y2]G[x1][y2]G[x1][y3].;else if(w1) G[x][y]G[x1][y]G[x2][y]G[x2][y-1]G[x3][y-1].;else if(w2) G[x][y]G[x][y1]G[x1][y1]G[x1][y2]G[x1][y3].;else if(w3) G[x][y]G[x1][y]G[x1][y-1]G[x2][y-1]G[x3][y-1].;else if(w4) G[x][y]G[x][y1]G[x][y2]G[x1][y]G[x1][y-1].;else if(w5) G[x][y]G[x1][y]G[x2][y]G[x2][y1]G[x3][y1].;else if(w6) G[x][y]G[x][y1]G[x1][y]G[x1][y-1]G[x1][y-2].;else if(w7) G[x][y]G[x1][y]G[x1][y1]G[x2][y1]G[x3][y1].;}else if(zJ) G[x][y]G[x1][y]G[x1][y-1]G[x1][y1]G[x2][y].;else if(zK){if(w0) G[x][y]G[x1][y]G[x1][y1]G[x2][y1]G[x2][y2].;else if(w1) G[x][y]G[x][y1]G[x1][y]G[x1][y-1]G[x2][y-1].;else if(w2) G[x][y]G[x][y1]G[x1][y1]G[x1][y2]G[x2][y2].;else if(w3) G[x][y]G[x1][y]G[x1][y-1]G[x2][y-1]G[x2][y-2].;}else if(zL){if(w0) G[x][y]G[x][y1]G[x][y2]G[x][y3]G[x1][y].;else if(w1) G[x][y]G[x][y1]G[x1][y1]G[x2][y1]G[x3][y1].;else if(w2) G[x][y]G[x1][y]G[x1][y-1]G[x1][y-2]G[x1][y-3].;else if(w3) G[x][y]G[x1][y]G[x2][y]G[x3][y]G[x3][y1].;else if(w4) G[x][y]G[x1][y]G[x1][y1]G[x1][y2]G[x1][y3].;else if(w5) G[x][y]G[x][y1]G[x1][y]G[x2][y]G[x3][y].;else if(w6) G[x][y]G[x][y1]G[x][y2]G[x][y3]G[x1][y3].;else if(w7) G[x][y]G[x1][y]G[x2][y]G[x3][y]G[x3][y-1].;}
}
int ltk(int x,int y)
{hjj[x][y]true;int re1;if(G[x-1][y].!hjj[x-1][y]) reltk(x-1,y);if(G[x][y-1].!hjj[x][y-1]) reltk(x,y-1);if(G[x1][y].!hjj[x1][y]) reltk(x1,y);if(G[x][y1].!hjj[x][y1]) reltk(x,y1);return re;
}
bool dfs(int x,int y)
{memset(hjj,false,sizeof hjj);for(int i1;i10;i)for(int j1;ji;j)if(G[i][j].!hjj[i][j])if(ltk(i,j)2) return false;for(char iA;iL;i){if(vis[i-A]) continue;for(int w0;w8;w)if(judge(x,y,i,w)){vis[i-A]true;fill(x,y,i,w);bool flagfalse;for(int j1;j10;j){for(int k1;kj;k)if(G[j][k].){flagtrue;if(dfs(j,k)) return true;break;}if(flag) break;}if(!flag) return true;vis[i-A]false;unfill(x,y,i,w);}}return false;
}
int main()
{for(int i1;i10;i){for(int j1;ji;j){G[i][j]readc();if(isalpha(G[i][j])) vis[G[i][j]-A]true;}for(int ji1;j10;j)G[i][j]$;}for(int i0;i11;i) G[i][0]G[i][11]G[0][i]G[11][i]$;for(int i1;i10;i)for(int j1;ji;j)if(G[i][j].){if(dfs(i,j)) print();else printf(No solution);return 0;}
} 转载于:https://www.cnblogs.com/coder-Uranus/p/9805366.html
