众筹平台网站搭建,如何快速建立网站,合作客户北京网站建设,页游排行一、题目
剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。 现在你要从中剪下5张来#xff0c;要求必须是连着的。 #xff08;仅仅连接一个角不算相连#xff09; 比如#xff0c;【图2.jpg】#xff0c;【图3.jpg】中#xff0c;粉红色所示部分就是合格的剪取。…一、题目
剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。 现在你要从中剪下5张来要求必须是连着的。 仅仅连接一个角不算相连 比如【图2.jpg】【图3.jpg】中粉红色所示部分就是合格的剪取。
请你计算一共有多少种不同的剪取方法。
请填写表示方案数目的整数。 注意你提交的应该是一个整数不要填写任何多余的内容或说明性文字。
按顺序的图1-3 二、代码 package Lan2016;public class G减邮票 {/*有12张连在一起的12生肖的邮票。现在你要从中剪下5张来要求必须是连着的。仅仅连接一个角不算相连粉红色所示部分就是合格的剪取。请你计算一共有多少种不同的剪取方法这仅仅是部分题目因为没有图*//** 大致思路我们五层for循环遍历每一个邮票并找到5个符合条件的* 对于像网格、迷宫之类的问题我们采用深度优先遍历的思想将每一个格子遍历但是不会重复的遍历** *///1.定义数组来存放这些格子定义一个计数器用来存最后的减去方法个数定义用来表示格子数static boolean[] arr new boolean[13];//定义为boolean类型表示是被选中还是不选中有两种情况//数组的长度为13因为从1到12 表示12张邮票下标0没有被使用static int count;static int n;//2.主函数public static void main(String args[]){//五层for循环遍历每一个方格从1到12for(int x1 1; x1 12; x1){for(int x2 x1 1; x2 12; x2 ){for(int x3 x2 1; x3 12; x3 ){for(int x4 x3 1; x4 12; x4 ){for(int x5 x41; x5 12;x5 ){//将所选中的格子赋值为true表示被选中arr[x1] arr[x2] arr[x3]arr[x4]arr[x5]true;n0;//调用dfs方法来找这五个格子dfs(x1);//传入i的原因是因为从树或图的根节点开始向下遍历//如果n5表示选好了,计数器加一if(n 5){count;}arr[x1] arr[x2] arr[x3]arr[x4]arr[x5]false;//看当前的5个各自是否符合条件后需要将数组都赋值false便于下一次的遍历}}}}}System.out.println(count);//输出计数器}//定义dfs函数static void dfs(int m){//要写参数//因为循环的时候我们把数组中的某些的元素已经赋值为true//对于找到的目前的格子我们赋值为falsearr[m] false;n;//找到一个格子将格子数加一//判断当前节点的左边一个节点是否被访问过如果没有被访问则去访问if(m ! 1 m ! 5 m ! 9 arr[m-1])dfs(m-1);//访问当前节点的右边一个节点是否被访问如果没访问则去访问if(m ! 4 m! 8 m ! 12 arr[m1])dfs(m1);//访问当前节点的上一个节点是否被访问如果没访问则去访问if(m ! 1 m ! 2 m ! 3 m ! 4 arr[m-4])dfs(m-4);//访问当前节点的上一个节点如果没有被访问则去访问if(m ! 9 m ! 10 m ! 11 m ! 12 arr[m 4])dfs(m4);}}三、反思 1.for循环用来找到五个不同的格子并赋值true每次找之前都要将n(找到的不相邻的方格数)都要赋值为0便于我们重新找的时候给n,n5的时候说明已经找到 2.dfs是为了找到这不相邻的五个格子从当前的格子往 上下左右去找相邻的格子当是ture的时候,表明这是我们for循环里选过的我们赋值false并n,再从相邻的格子递归找下去若找到的正是我们选过的那么n就等于5我们count
