题面
题目链接
题目描述
智慧珠游戏拼盘由一个三角形盘件和 12 个形态各异的零件组成。拼盘的盘 件如图1所示
![洛谷 P4205 [NOI2005]智慧珠游戏 DFS](https://image.shishitao.com:8440/aHR0cDovL2Jic21heC5pa2FmYW4uY29tL3N0YXRpYy9MM0J5YjNoNUwyaDBkSEJ6TDJOa2JpNXNkVzluZFM1dmNtY3ZkWEJzYjJGa0wzQnBZeTh4TXpjMk55NXdibWM9LmpwZw%3D%3D.jpg?w=700 "洛谷 P4205 [NOI2005]智慧珠游戏 DFS")
![洛谷 P4205 [NOI2005]智慧珠游戏 DFS](https://image.shishitao.com:8440/aHR0cDovL2Jic21heC5pa2FmYW4uY29tL3N0YXRpYy9MM0J5YjNoNUwyaDBkSEJ6TDJOa2JpNXNkVzluZFM1dmNtY3ZkWEJzYjJGa0wzQnBZeTh4TXpjMk9DNXdibWM9LmpwZw%3D%3D.jpg?w=700 "洛谷 P4205 [NOI2005]智慧珠游戏 DFS")
![洛谷 P4205 [NOI2005]智慧珠游戏 DFS](https://image.shishitao.com:8440/aHR0cDovL2Jic21heC5pa2FmYW4uY29tL3N0YXRpYy9MM0J5YjNoNUwyaDBkSEJ6TDJOa2JpNXNkVzluZFM1dmNtY3ZkWEJzYjJGa0wzQnBZeTh4TXpjMk9TNXdibWM9LmpwZw%3D%3D.jpg?w=700 "洛谷 P4205 [NOI2005]智慧珠游戏 DFS")
对于由珠子构成的零件，可以放到盘件的任一位置，条件是能有地方放，且尺寸合适，所有的零件都允许旋转(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
说明
1000ms,128MB
思路
请手打暴搜（听说可以舞蹈链，但我不会）
另外，可以先判连通块大小优化一下，如果有连通块大小小于等于2，那肯定无解
AC代码
#include<bits/stdc++.h>
#define ok =='.'
#define tr =ch
#define cl ='.'
using namespace std;
char MAP[20][20];
bool vis[15],VIS[20][20];
int num[20][20];
int DFS(int x,int y)
{
if(VIS[x][y]) return 0;
VIS[x][y]=1;
if(MAP[x][y]!='.') return 0;
return 1+DFS(x+1,y)+DFS(x-1,y)+DFS(x,y+1)+DFS(x,y-1);
}
void dfs(int x,int y)
{
if(x==11)
{
for(int i=1;i<=10;i++)
{
for(int j=1;j<=i;j++)
cout<<MAP[i][j];
cout<<endl;
}
exit(0);
}
if(y==x+1) {dfs(x+1,1);return;}
if(!(MAP[x][y]ok)) {dfs(x,y+1);return;}
char ch;
ch='J';
if(!vis[10])
{
vis[10]=true;MAP[x][y]tr;
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+1][y-1]ok && MAP[x+1][y+1]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+1][y-1]tr,MAP[x+1][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+1][y-1]cl,MAP[x+1][y+1]cl;
}
vis[10]=false;MAP[x][y]cl;
}
ch='D';
if(!vis[4])
{
vis[4]=true;MAP[x][y]tr;
if(MAP[x+1][y]ok && MAP[x][y+1]ok && MAP[x+1][y+1]ok)
{
MAP[x+1][y]tr,MAP[x][y+1]tr,MAP[x+1][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x][y+1]cl,MAP[x+1][y+1]cl;
}
vis[4]=false;MAP[x][y]cl;
}
ch='B';
if(!vis[2])
{
vis[2]=true;MAP[x][y]tr;
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+3][y]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+3][y]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+3][y]cl;
}
if(MAP[x][y+1]ok && MAP[x][y+2]ok && MAP[x][y+3]ok)
{
MAP[x][y+1]tr,MAP[x][y+2]tr,MAP[x][y+3]tr;
dfs(x,y+1);
MAP[x][y+1]cl,MAP[x][y+2]cl,MAP[x][y+3]cl;
}
vis[2]=false;MAP[x][y]cl;
}
ch='K';
if(!vis[11])
{
vis[11]=true;MAP[x][y]tr;
if(MAP[x+1][y]ok && MAP[x+1][y+1]ok && MAP[x+2][y+1]ok && MAP[x+2][y+2]ok)
{
MAP[x+1][y]tr,MAP[x+1][y+1]tr,MAP[x+2][y+1]tr,MAP[x+2][y+2]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y+1]cl,MAP[x+2][y+1]cl,MAP[x+2][y+2]cl;
}
if(MAP[x][y+1]ok && MAP[x+1][y+1]ok && MAP[x+1][y+2]ok && MAP[x+2][y+2]ok)
{
MAP[x][y+1]tr,MAP[x+1][y+1]tr,MAP[x+1][y+2]tr,MAP[x+2][y+2]tr;
dfs(x,y+1);
MAP[x][y+1]cl,MAP[x+1][y+1]cl,MAP[x+1][y+2]cl,MAP[x+2][y+2]cl;
}
if(y>2 && MAP[x+1][y]ok && MAP[x+1][y-1]ok && MAP[x+2][y-1]ok && MAP[x+2][y-2]ok)
{
MAP[x+1][y]tr,MAP[x+1][y-1]tr,MAP[x+2][y-1]tr,MAP[x+2][y-2]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y-1]cl,MAP[x+2][y-1]cl,MAP[x+2][y-2]cl;
}
if(MAP[x+1][y]ok && MAP[x+1][y-1]ok && MAP[x+2][y-1]ok && MAP[x+1][y]ok)
{
MAP[x+1][y]tr,MAP[x+1][y-1]tr,MAP[x+2][y-1]tr,MAP[x+1][y]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y-1]cl,MAP[x+2][y-1]cl,MAP[x+1][y]cl;
}
vis[11]=false;MAP[x][y]cl;
}
ch='G';
if(!vis[7])
{
vis[7]=true;MAP[x][y]tr;
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x][y+1]ok && MAP[x+2][y+1]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x][y+1]tr,MAP[x+2][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x][y+1]cl,MAP[x+2][y+1]cl;
}
if(MAP[x+1][y+1]ok && MAP[x+2][y]ok && MAP[x][y+1]ok && MAP[x+2][y+1]ok)
{
MAP[x+1][y+1]tr,MAP[x+2][y]tr,MAP[x][y+1]tr,MAP[x+2][y+1]tr;
dfs(x,y+1);
MAP[x+1][y+1]cl,MAP[x+2][y]cl,MAP[x][y+1]cl,MAP[x+2][y+1]cl;
}
if(MAP[x][y+1]ok && MAP[x][y+2]ok && MAP[x+1][y+2]ok && MAP[x+1][y]ok)
{
MAP[x][y+1]tr,MAP[x][y+2]tr,MAP[x+1][y+2]tr,MAP[x+1][y]tr;
dfs(x,y+1);
MAP[x][y+1]cl,MAP[x][y+2]cl,MAP[x+1][y+2]cl,MAP[x+1][y]cl;
}
if(MAP[x+1][y+1]ok && MAP[x][y+2]ok && MAP[x+1][y+2]ok && MAP[x+1][y]ok)
{
MAP[x+1][y+1]tr,MAP[x][y+2]tr,MAP[x+1][y+2]tr,MAP[x+1][y]tr;
dfs(x,y+1);
MAP[x+1][y+1]cl,MAP[x][y+2]cl,MAP[x+1][y+2]cl,MAP[x+1][y]cl;
}
vis[7]=false;MAP[x][y]cl;
}
ch='E';
if(!vis[5])
{
vis[5]=true;MAP[x][y]tr;
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x][y+1]ok && MAP[x][y+2]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x][y+1]tr,MAP[x][y+2]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x][y+1]cl,MAP[x][y+2]cl;
}
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+2][y+1]ok && MAP[x+2][y+2]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+2][y+1]tr,MAP[x+2][y+2]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+2][y+1]cl,MAP[x+2][y+2]cl;
}
if(y>2 && MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+2][y-1]ok && MAP[x+2][y-2]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+2][y-1]tr,MAP[x+2][y-2]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+2][y-1]cl,MAP[x+2][y-2]cl;
}
if(MAP[x+2][y+1]ok && MAP[x+2][y+2]ok && MAP[x+1][y]ok && MAP[x+2][y]ok)
{
MAP[x+2][y+1]tr,MAP[x+2][y+2]tr,MAP[x+1][y]tr,MAP[x+2][y]tr;
dfs(x,y+1);
MAP[x+2][y+1]cl,MAP[x+2][y+2]cl,MAP[x+1][y]cl,MAP[x+2][y]cl;
}
vis[5]=false;MAP[x][y]cl;
}
ch='A';
if(!vis[1])
{
vis[1]=true;MAP[x][y]tr;
if(MAP[x+1][y]ok && MAP[x][y+1]ok)
{
MAP[x+1][y]tr,MAP[x][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x][y+1]cl;
}
if(MAP[x+1][y+1]ok && MAP[x][y+1]ok)
{
MAP[x+1][y+1]tr,MAP[x][y+1]tr;
dfs(x,y+1);
MAP[x+1][y+1]cl,MAP[x][y+1]cl;
}
if(MAP[x+1][y]ok && MAP[x+1][y+1]ok)
{
MAP[x+1][y]tr,MAP[x+1][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y+1]cl;
}
if(MAP[x+1][y]ok && MAP[x+1][y-1]ok)
{
MAP[x+1][y]tr,MAP[x+1][y-1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y-1]cl;
}
vis[1]=false;MAP[x][y]cl;
}
ch='I';
if(!vis[9])
{
vis[9]=true;MAP[x][y]tr;
if(MAP[x+1][y+1]ok && MAP[x][y+1]ok && MAP[x+1][y+2]ok && MAP[x+1][y+3]ok)
{
MAP[x+1][y+1]tr,MAP[x][y+1]tr,MAP[x+1][y+2]tr,MAP[x+1][y+3]tr;
dfs(x,y+1);
MAP[x+1][y+1]cl,MAP[x][y+1]cl,MAP[x+1][y+2]cl,MAP[x+1][y+3]cl;
}
if(MAP[x+1][y]ok && MAP[x+1][y-1]ok && MAP[x][y+2]ok && MAP[x][y+1]ok)
{
MAP[x+1][y]tr,MAP[x+1][y-1]tr,MAP[x][y+2]tr,MAP[x][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y-1]cl,MAP[x][y+2]cl,MAP[x][y+1]cl;
}
if(MAP[x+1][y+2]ok && MAP[x][y+1]ok && MAP[x][y+2]ok && MAP[x+1][y+3]ok)
{
MAP[x+1][y+2]tr,MAP[x][y+1]tr,MAP[x][y+2]tr,MAP[x+1][y+3]tr;
dfs(x,y+1);
MAP[x+1][y+2]cl,MAP[x][y+1]cl,MAP[x][y+2]cl,MAP[x+1][y+3]cl;
}
if(y>2 && MAP[x+1][y]ok && MAP[x][y+1]ok && MAP[x+1][y-2]ok && MAP[x+1][y-1]ok)
{
MAP[x+1][y]tr,MAP[x][y+1]tr,MAP[x+1][y-2]tr,MAP[x+1][y-1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x][y+1]cl,MAP[x+1][y-2]cl,MAP[x+1][y-1]cl;
}
if(MAP[x+2][y]ok && MAP[x+1][y]ok && MAP[x+2][y+1]ok && MAP[x+3][y+1]ok)
{
MAP[x+2][y]tr,MAP[x+1][y]tr,MAP[x+2][y+1]tr,MAP[x+3][y+1]tr;
dfs(x,y+1);
MAP[x+2][y]cl,MAP[x+1][y]cl,MAP[x+2][y+1]cl,MAP[x+3][y+1]cl;
}
if(MAP[x+1][y+1]ok && MAP[x+1][y]ok && MAP[x+2][y+1]ok && MAP[x+3][y+1]ok)
{
MAP[x+1][y+1]tr,MAP[x+1][y]tr,MAP[x+2][y+1]tr,MAP[x+3][y+1]tr;
dfs(x,y+1);
MAP[x+1][y+1]cl,MAP[x+1][y]cl,MAP[x+2][y+1]cl,MAP[x+3][y+1]cl;
}
if(MAP[x+2][y]ok && MAP[x+1][y]ok && MAP[x+2][y-1]ok && MAP[x+3][y-1]ok)
{
MAP[x+2][y]tr,MAP[x+1][y]tr,MAP[x+2][y-1]tr,MAP[x+3][y-1]tr;
dfs(x,y+1);
MAP[x+2][y]cl,MAP[x+1][y]cl,MAP[x+2][y-1]cl,MAP[x+3][y-1]cl;
}
if(MAP[x+1][y-1]ok && MAP[x+1][y]ok && MAP[x+2][y-1]ok && MAP[x+3][y-1]ok)
{
MAP[x+1][y-1]tr,MAP[x+1][y]tr,MAP[x+2][y-1]tr,MAP[x+3][y-1]tr;
dfs(x,y+1);
MAP[x+1][y-1]cl,MAP[x+1][y]cl,MAP[x+2][y-1]cl,MAP[x+3][y-1]cl;
}
vis[9]=false;MAP[x][y]cl;
}
ch='H';
if(!vis[8])
{
vis[8]=true;MAP[x][y]tr;
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+1][y+1]ok && MAP[x+2][y+1]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+1][y+1]tr,MAP[x+2][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+1][y+1]cl,MAP[x+2][y+1]cl;
}
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+1][y-1]ok && MAP[x+2][y-1]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+1][y-1]tr,MAP[x+2][y-1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+1][y-1]cl,MAP[x+2][y-1]cl;
}
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+1][y+1]ok && MAP[x][y+1]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+1][y+1]tr,MAP[x][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+1][y+1]cl,MAP[x][y+1]cl;
}
if(MAP[x+1][y]ok && MAP[x+2][y+1]ok && MAP[x+1][y+1]ok && MAP[x][y+1]ok)
{
MAP[x+1][y]tr,MAP[x+2][y+1]tr,MAP[x+1][y+1]tr,MAP[x][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y+1]cl,MAP[x+1][y+1]cl,MAP[x][y+1]cl;
}
if(MAP[x+1][y]ok && MAP[x][y+1]ok && MAP[x+1][y+1]ok && MAP[x][y+2]ok)
{
MAP[x+1][y]tr,MAP[x][y+1]tr,MAP[x+1][y+1]tr,MAP[x][y+2]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x][y+1]cl,MAP[x+1][y+1]cl,MAP[x][y+2]cl;
}
if(MAP[x+1][y]ok && MAP[x][y+1]ok && MAP[x+1][y+1]ok && MAP[x+1][y+2]ok)
{
MAP[x+1][y]tr,MAP[x][y+1]tr,MAP[x+1][y+1]tr,MAP[x+1][y+2]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x][y+1]cl,MAP[x+1][y+1]cl,MAP[x+1][y+2]cl;
}
if(MAP[x][y+2]ok && MAP[x][y+1]ok && MAP[x+1][y+1]ok && MAP[x+1][y+2]ok)
{
MAP[x][y+2]tr,MAP[x][y+1]tr,MAP[x+1][y+1]tr,MAP[x+1][y+2]tr;
dfs(x,y+1);
MAP[x][y+2]cl,MAP[x][y+1]cl,MAP[x+1][y+1]cl,MAP[x+1][y+2]cl;
}
if(MAP[x+1][y]ok && MAP[x][y+1]ok && MAP[x+1][y+1]ok && MAP[x+1][y-1]ok)
{
MAP[x+1][y]tr,MAP[x][y+1]tr,MAP[x+1][y+1]tr,MAP[x+1][y-1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x][y+1]cl,MAP[x+1][y+1]cl,MAP[x+1][y-1]cl;
}
vis[8]=false;MAP[x][y]cl;
}
ch='F';
if(!vis[6])
{
vis[6]=true;MAP[x][y]tr;
if(MAP[x+1][y+1]ok && MAP[x][y+1]ok && MAP[x][y+2]ok && MAP[x][y+3]ok)
{
MAP[x+1][y+1]tr,MAP[x][y+1]tr,MAP[x][y+2]tr,MAP[x][y+3]tr;
dfs(x,y+1);
MAP[x+1][y+1]cl,MAP[x][y+1]cl,MAP[x][y+2]cl,MAP[x][y+3]cl;
}
if(MAP[x+1][y+2]ok && MAP[x][y+1]ok && MAP[x][y+2]ok && MAP[x][y+3]ok)
{
MAP[x+1][y+2]tr,MAP[x][y+1]tr,MAP[x][y+2]tr,MAP[x][y+3]tr;
dfs(x,y+1);
MAP[x+1][y+2]cl,MAP[x][y+1]cl,MAP[x][y+2]cl,MAP[x][y+3]cl;
}
if(MAP[x+1][y+1]ok && MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+3][y]ok)
{
MAP[x+1][y+1]tr,MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+3][y]tr;
dfs(x,y+1);
MAP[x+1][y+1]cl,MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+3][y]cl;
}
if(MAP[x+2][y+1]ok && MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+3][y]ok)
{
MAP[x+2][y+1]tr,MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+3][y]tr;
dfs(x,y+1);
MAP[x+2][y+1]cl,MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+3][y]cl;
}
if(MAP[x+1][y-1]ok && MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+3][y]ok)
{
MAP[x+1][y-1]tr,MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+3][y]tr;
dfs(x,y+1);
MAP[x+1][y-1]cl,MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+3][y]cl;
}
if(MAP[x+2][y-1]ok && MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+3][y]ok)
{
MAP[x+2][y-1]tr,MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+3][y]tr;
dfs(x,y+1);
MAP[x+2][y-1]cl,MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+3][y]cl;
}
if(MAP[x+1][y]ok && MAP[x+1][y+1]ok && MAP[x+1][y+2]ok && MAP[x+1][y-1]ok)
{
MAP[x+1][y]tr,MAP[x+1][y+1]tr,MAP[x+1][y+2]tr,MAP[x+1][y-1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y+1]cl,MAP[x+1][y+2]cl,MAP[x+1][y-1]cl;
}
if(y>2 && MAP[x+1][y]ok && MAP[x+1][y+1]ok && MAP[x+1][y-2]ok && MAP[x+1][y-1]ok)
{
MAP[x+1][y]tr,MAP[x+1][y+1]tr,MAP[x+1][y-2]tr,MAP[x+1][y-1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y+1]cl,MAP[x+1][y-2]cl,MAP[x+1][y-1]cl;
}
vis[6]=false;MAP[x][y]cl;
}
ch='L';
if(!vis[12])
{
vis[12]=true;MAP[x][y]tr;
if(MAP[x+1][y]ok && MAP[x][y+1]ok && MAP[x][y+2]ok && MAP[x][y+3]ok)
{
MAP[x+1][y]tr,MAP[x][y+1]tr,MAP[x][y+2]tr,MAP[x][y+3]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x][y+1]cl,MAP[x][y+2]cl,MAP[x][y+3]cl;
}
if(MAP[x+1][y]ok && MAP[x+1][y+1]ok && MAP[x+1][y+2]ok && MAP[x+1][y+3]ok)
{
MAP[x+1][y]tr,MAP[x+1][y+1]tr,MAP[x+1][y+2]tr,MAP[x+1][y+3]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y+1]cl,MAP[x+1][y+2]cl,MAP[x+1][y+3]cl;
}
if(y>3 && MAP[x+1][y]ok && MAP[x+1][y-1]ok && MAP[x+1][y-2]ok && MAP[x+1][y-3]ok)
{
MAP[x+1][y]tr,MAP[x+1][y-1]tr,MAP[x+1][y-2]tr,MAP[x+1][y-3]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y-1]cl,MAP[x+1][y-2]cl,MAP[x+1][y-3]cl;
}
if(MAP[x+1][y+3]ok && MAP[x][y+1]ok && MAP[x][y+2]ok && MAP[x][y+3]ok)
{
MAP[x+1][y+3]tr,MAP[x][y+1]tr,MAP[x][y+2]tr,MAP[x][y+3]tr;
dfs(x,y+1);
MAP[x+1][y+3]cl,MAP[x][y+1]cl,MAP[x][y+2]cl,MAP[x][y+3]cl;
}
if(MAP[x][y+1]ok && MAP[x+1][y+1]ok && MAP[x+2][y+1]ok && MAP[x+3][y+1]ok)
{
MAP[x][y+1]tr,MAP[x+1][y+1]tr,MAP[x+2][y+1]tr,MAP[x+3][y+1]tr;
dfs(x,y+1);
MAP[x][y+1]cl,MAP[x+1][y+1]cl,MAP[x+2][y+1]cl,MAP[x+3][y+1]cl;
}
if(MAP[x][y+1]ok && MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+3][y]ok)
{
MAP[x][y+1]tr,MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+3][y]tr;
dfs(x,y+1);
MAP[x][y+1]cl,MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+3][y]cl;
}
if(MAP[x+3][y-1]ok && MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+3][y]ok)
{
MAP[x+3][y-1]tr,MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+3][y]tr;
dfs(x,y+1);
MAP[x+3][y-1]cl,MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+3][y]cl;
}
if(MAP[x+3][y+1]ok && MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+3][y]ok)
{
MAP[x+3][y+1]tr,MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+3][y]tr;
dfs(x,y+1);
MAP[x+3][y+1]cl,MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+3][y]cl;
}
vis[12]=false;MAP[x][y]cl;
}
ch='C';
if(!vis[3])
{
vis[3]=true;MAP[x][y]tr;
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x][y+1]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x][y+1]cl;
}
if(MAP[x+1][y]ok && MAP[x+1][y+1]ok && MAP[x+1][y+2]ok)
{
MAP[x+1][y]tr,MAP[x+1][y+1]tr,MAP[x+1][y+2]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y+1]cl,MAP[x+1][y+2]cl;
}
if(y>2 && MAP[x+1][y]ok && MAP[x+1][y-1]ok && MAP[x+1][y-2]ok)
{
MAP[x+1][y]tr,MAP[x+1][y-1]tr,MAP[x+1][y-2]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+1][y-1]cl,MAP[x+1][y-2]cl;
}
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+2][y+1]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+2][y+1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+2][y+1]cl;
}
if(MAP[x+1][y]ok && MAP[x][y+1]ok && MAP[x][y+2]ok)
{
MAP[x+1][y]tr,MAP[x][y+1]tr,MAP[x][y+2]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x][y+1]cl,MAP[x][y+2]cl;
}
if(MAP[x+1][y]ok && MAP[x+2][y]ok && MAP[x+2][y-1]ok)
{
MAP[x+1][y]tr,MAP[x+2][y]tr,MAP[x+2][y-1]tr;
dfs(x,y+1);
MAP[x+1][y]cl,MAP[x+2][y]cl,MAP[x+2][y-1]cl;
}
if(MAP[x][y+1]ok && MAP[x][y+2]ok && MAP[x+1][y+2]ok)
{
MAP[x][y+1]tr,MAP[x][y+2]tr,MAP[x+1][y+2]tr;
dfs(x,y+1);
MAP[x][y+1]cl,MAP[x][y+2]cl,MAP[x+1][y+2]cl;
}
if(MAP[x][y+1]ok && MAP[x+1][y+1]ok && MAP[x+2][y+1]ok)
{
MAP[x][y+1]tr,MAP[x+1][y+1]tr,MAP[x+2][y+1]tr;
dfs(x,y+1);
MAP[x][y+1]cl,MAP[x+1][y+1]cl,MAP[x+2][y+1]cl;
}
vis[3]=false;MAP[x][y]cl;
}
}
int main()
{
for(int i=1;i<=10;i++)
for(int j=1;j<=i;j++)
{
cin>>MAP[i][j];
if(MAP[i][j]>='A' && MAP[i][j]<='L') vis[MAP[i][j]-'A'+1]=true;
}
for(int i=1;i<=10;i++)
for(int j=1;j<=i;j++)
{
int n=DFS(i,j);
if(n && n<=2) goto lskakioi;
}
dfs(1,1);
lskakioi:
printf("No solution");
return 0;
}
总结
这是今天考试题。。。下来一看，错了8个地方，时间也浪费了。所以这种长的题，就应该多检查几遍。
（感觉有写猪国杀的动力了）
洛谷 P4205 [NOI2005]智慧珠游戏 DFS的更多相关文章
-
Luogu P4205 [NOI2005]智慧珠游戏
国内少有的可以练习神仙算法--DLX的好题怎么可以被爆搜埋没呢? 看到这题没有DLX的题解所以写一篇,不过貌似我实现的太弱(构图太慢)所以速度上不是很快. 下面开始讲题,但请保证你要先学会DLX.(d ...
-
bzoj 1501: [NOI2005]智慧珠游戏 Dancing Link
1501: [NOI2005]智慧珠游戏 Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 190 Solved: 122[Submit][Status] ...
-
【搜索好题】bzoj1501 [NOI2005]智慧珠游戏
bzoj1501 [NOI2005]智慧珠游戏 搜索苟逼题系列. 暴力枚举每一种情况(包括旋转翻转全都考虑在内)然后码出代码. (正解似乎不是这样子的) 那年好像还有平衡树苟逼题维护数列233333心 ...
-
[BZOJ1501][NOI2005] 智慧珠游戏
Input 文件中包含初始的盘件描述,一共有10行,第i行有i个字符.如果第i行的第j个字符是字母”A”至”L”中的一个,则表示第i行第j列的格子上已经放了零件,零件的编号为对应的字母.如果第i行的第 ...
-
洛谷OJ P2356 弹珠游戏 维护前缀和
题目描述 Description MedalPluS 和他的小伙伴 NOIRP 发掘了一个骨灰级别的游戏--超级弹珠. 游戏的内容是:在一个 n*n 的矩阵里,有若干个敌人,你的弹珠可以摧毁敌人,但只 ...
-
洛谷 P2356 【弹珠游戏】题解
自我感觉应该没有用结构体做的吧 这道题其实非常水 很适合初学贪心的同学做一下 我好像没有用贪心做,嘻嘻 首先先读题, 题目中说这个游戏只能消灭当前所在位置的行.列的敌人 首先特判一下: if(tt== ...
-
【BZOJ1501】【NOI2005】智慧珠游戏（搜索）
[BZOJ1501][NOI2005]智慧珠游戏(搜索) 题面 我要一改我懒惰的作风 这道题目必须放题面 Description Input 文件中包含初始的盘件描述,一共有10行,第i行有i个字符. ...
-
洛谷 P1219 八皇后【经典DFS，温习搜索】
P1219 八皇后 题目描述 检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行.每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子. 上面的布局可以用序 ...
-
洛谷P1219 ：八皇后（DFS+回溯）
题目描述 检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行.每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子. 上面的布局可以用序列2 4 6 1 3 ...
随机推荐
-
2015.4.21 实现一般免登陆，微博QQ分享，字体自适应等
1.实现一般的登录验证和免登陆: 解决方法:node方法代码,nodeJS实现的session模块,不完整,但能用,仅供参考. 语言无所谓,session的机制都是一样的,实现不一样而已,: 2. ...
-
区分debug和release生成文件的名称
通常我们编译工程按照debug和release区分,且明确在Debug版本的生成文件中加入d标记.譬如: HelloWorld.exe 一般是release的生成文件,而debug版叫:HelloWo ...
-
python——协程
由于python中的多线程比较特殊,所以协程的概念就变得尤为珍贵了,对于cpu密集型的操作,使用协程的效率无疑要好过多线程很多.因为协程的创建及其间切换的时间成本要低于线程很多.也因为这一点,很多人说 ...
-
<;postfix邮件服务下mysql的升级>;
本片服务的环境的红帽的企业版6.5 的,6.3的测试可能会略有不一样,不过方法大致是一样的. 当前系统的postfix的版本为 postfix-2.6.6-2.2.el6_1.x86_64 我们要向使 ...
-
基于JAVA WEB的医药管理系统
学习上可以模仿,但是不可以抄袭! 附加百度链接:http://wenku.baidu.com/link?url=_r44vGCi8pcm6o44YCvkcHGoT_XhB8jURnweao2YVo1j ...
-
virtalBox共享文件夹设置
sudo mount -t vboxsf gongxiang /mnt/shared/
-
51NOD 1222&#160;最小公倍数计数 [莫比乌斯反演 杜教筛]
1222 最小公倍数计数 题意:求有多少数对\((a,b):a<b\)满足\(lcm(a,b) \in [1, n]\) \(n \le 10^{11}\) 卡内存! 枚举\(gcd, \fra ...
-
ProgressBar的简单使用
当我们的应用在进行耗时操作时,显示一个进度条呈现给用户,让用户知道当前进度是一个很好的体验,接下来我们就来简单了解下ProgressBar(本文主要针对初学者,大神可以绕开啦),先看效果图: 进度条P ...
-
4.html基础标签：表单
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...
-
Codeforces round 1083
Div1 526 这个E考试的时候没调出来真的是耻辱.jpg A 求个直径就完事 #include<cstdio> #include<algorithm> #include&l ...