1286:[蓝桥杯2016初赛]剪邮票中/全排列/dfs/连通块

篇首语：本文由编程笔记#小编为大家整理，主要介绍了1286: [蓝桥杯2016初赛]剪邮票 中 / 全排列 / dfs / 连通块相关的知识，希望对你有一定的参考价值。

http://oj.ecustacm.cn/problem.php?id&＃61;1286

直接用dfs 是不可以的因为 dfs只可以走L型 不可以走T型
那么我们可以先用现有的全排列函数把所有的情况列出来&＃xff0c;再判断其可不可以连通。

首先关键的一点在于将一位的数组映射到二维。
第二点就是如何判断是连通的
关于第二点就是用两个数组保存各个的方向。
如果可以走的话就把 1 恢复为 0 。
如果这个动作按照方向执行了5次说明就是连通的。


#include<iostream>
#include
#include
#include
using namespace std;
int a[12]&＃61;0,0,0,0,0,0,0,1,1,1,1,1;//一维
int b[5][5];//二维
int xx[]&＃61;-1,1,0,0;//x方向
int yy[]&＃61;0,0,1,-1;//y方向
int ans;//总的方法
int cnt;//统计走的次数
void dfs(int x,int y)

if(x<0||x>2||y<0||y>3) return; //越界退出
if(b[x][y]!&＃61;1) return; //不可以走
cnt&＃43;&＃43;;//走的步数加1

if(cnt&＃61;&＃61;5)//走了5步&＃xff0c;说明连通

ans&＃43;&＃43;;
return;


b[x][y]&＃61;0;//走过后恢复为0
for(int i&＃61;0;i<4;i&＃43;&＃43;)

x&＃61;x&＃43;xx[i];
y&＃61;y&＃43;yy[i];
dfs(x,y);

x&＃61;x-xx[i];//恢复现场
y&＃61;y-yy[i];


int main(void)

do

int x,y;
for(int i&＃61;0;i<3;i&＃43;&＃43;)

for(int j&＃61;0;j<4;j&＃43;&＃43;)

if(a[i*4&＃43;j]&＃61;&＃61;1)

x&＃61;i;
y&＃61;j;
b[i][j]&＃61;1;

else

b[i][j]&＃61;0;



dfs(x,y);
cnt&＃61;0;
while(next_permutation(a,a&＃43;12));
cout<<ans<<endl;
return 0;



另一种方法:

#include
using namespace std;
int a[]&＃61;0,0,0,0,0,0,0,1,1,1,1,1;
int g[3][4];
void dfs(int x,int y)

g[x][y]&＃61;0;
if(x-1>&＃61;0&&g[x-1][y]&＃61;&＃61;1)dfs(x-1,y);
if(x&＃43;1<3&&g[x&＃43;1][y]&＃61;&＃61;1)dfs(x&＃43;1,y);
if(y-1>&＃61;0&&g[x][y-1]&＃61;&＃61;1)dfs(x,y-1);
if(y&＃43;1<4&&g[x][y&＃43;1]&＃61;&＃61;1)dfs(x,y&＃43;1);

int check()

int ans&＃61;0;
for(int i&＃61;0;i<3;i&＃43;&＃43;)

for(int j&＃61;0;j<4;j&＃43;&＃43;)

if(g[i][j]&＃61;&＃61;1)

dfs(i,j);
ans&＃43;&＃43;;//连通块数



return ans&＃61;&＃61;1;//如果块数是1 说明是5个相连的

int main()

int ans&＃61;0;
do
for(int i&＃61;0;i<3;i&＃43;&＃43;)

for(int j&＃61;0;j<4;j&＃43;&＃43;)

if(a[i*4&＃43;j]&＃61;&＃61;1)

g[i][j]&＃61;1;

else
g[i][j]&＃61;0;



if(check())
ans&＃43;&＃43;;
while(next_permutation(a,a&＃43;12));
cout<<ans<<endl;
return 0;



#include
#include
#include
#include
#include
using namespace std;
int a[12]&＃61;0,0,0,0,0,0,0,1,1,1,1,1;
int map[5][5];
bool vis[5][5];
int dx[4]&＃61;-1,0,1,0;
int dy[4]&＃61;0,1,0,-1;
int ans;
int sum;
void dfs(int x,int y)

ans&＃43;&＃43;;
for(int i&＃61;0;i<4;i&＃43;&＃43;)

int tempx&＃61;x&＃43;dx[i];
int tempy&＃61;y&＃43;dy[i];
if(tempx>&＃61;0&&tempx<3&&tempy>&＃61;0&&tempy<4&&!vis[tempx][tempy]&&map[tempx][tempy]&＃61;&＃61;1)

vis[tempx][tempy]&＃61;true;
dfs(tempx,tempy);



int main(void)

do

int k&＃61;0;
int startx,starty;
for(int i&＃61;0;i<3;i&＃43;&＃43;)

for(int j&＃61;0;j<4;j&＃43;&＃43;)

map[i][j]&＃61;a[k&＃43;&＃43;];
if(map[i][j]&＃61;&＃61;1)

startx&＃61;i;
starty&＃61;j;



vis[startx][starty]&＃61;true;
dfs(startx,starty);
if(ans&＃61;&＃61;5) sum&＃43;&＃43;;
ans&＃61;0;
memset(vis,0,sizeof vis);
while(next_permutation(a,a&＃43;12));
cout<<sum<<endl;
return 0;