.png)
同时按几个按钮效果就会相互抵消
.png)
问题： 请你写一个程序, 确定需要按下哪些按钮, 恰好使得所 有的灯都熄灭2.解题1.输入 要解决的案例数 0 1 0 1...灯情况（1亮起，0不亮）2.输出 0 1 0 1...操作情况（1按下，0不按）3.分析 不同行的灯可以相互影响， 对第1行中每盏点亮的灯, 按下第2行对应的按钮, 就 可以熄灭第1行的全部灯 如此重复下去, 可以熄灭第1, 2, 3, 4行的全部灯 第一想法：将所有按钮状态一一枚举，判断最后是否全灭 （但是可能性有2^30可能，会超时） 灯最后的是亮是按取决于两个因素：1.当前行的按钮情况 2.下一行的按钮情况其他行根本就不会影响当前行的灯，所以第一行的按钮是没法预测的（随机的），当第一行的按钮情况确定之后，下一行就是唯一的了，依次类推下下行也是唯一的。所以我们要遍历的就是第一行的随机情况。 而判断是否全灭，就是当最后一行熄灭了前一行的所有灯之后，最后一行如果刚好全灭，说明所有的灯都熄灭了。否则第一行就得换状态。 第二想法：将第一行可能性枚举，下一行将固定，判断最后一行是否刚好全灭。（第一行的可能性：2^6=64） 优化想法：按列来枚举（第一行的可能性：2^5=32）4.具体实现 1.做两个数组，数组A用来表示灯亮显示，数组B用来表示按钮操作。 2.用六重循环，遍历第一行的每个数的两种可能。（想要简介的话，把第一行看做6位的二进制来算：用while来形成二级制的规律,尝试一下） 3.优化过程：解决0坐标开始和最后一个结束的问题，设立不用0坐标和最后一个的数组 4.判断这个灯亮不亮：取决于上面的灯处理之后的状态，而上面的灯的处理需要左右上的按钮和本身状态决定（除了第一行是随机的），所以用上面的四个影响因素（左右上的按钮和本身状态）加起来，如果是偶数，效果抵消，值为0。（所以用%计算）
.png)
5.当所有的数组存好之后，取出最后一列的上左右中按钮情况，判断与之前灯亮的关系，如果两者不相等，说明最终灯的状态是亮的，一旦有亮的出现，马上返回错误。（把核心步骤装到一个方法中）4.小结思路A获取灯亮情况调用B方法，枚举出不同的第一行输出所得到的数组B二进制的枚举第一行操作情况调用C方法，把枚举值传过去，根据返回结果，更换第一行C通过第一行获取其他行的操作情况验证最后一行与与灯亮的关系是否为灯灭，返回结果5.java代码实现package Test;import java.util.Scanner;/*枚举 熄灯问题 * 当按下一个按钮后, 该按钮以及周围位置(上边, 下边, 左 边, 右边)的灯都会改变一次（ 如果灯原来是点亮的, 就会被熄灭） * */public class Test { //检测排错！！！static int light[][]=new int[6][8]; //灯亮情况数组5行6列去外围(左右头尾);static int PRess[][]=new int[6][8]; //灯亮情况数组5行6列去外围(左右头尾);public static void main(String[] args) {// A/* * 测试数据： *0 1 1 0 1 01 0 0 1 1 10 0 1 0 0 11 0 0 1 0 10 1 1 1 0 0*/ System.out.println("请输入灯亮情况"); Scanner input=new Scanner(System.in); //获取输入数组：灯亮情况 for(int i=1;i<light.length;i++){ //行 for(int j=1;j<light[i].length-1;j++){ //列 light[i][j]=input.nextInt(); } } System.out.println("输入完毕"); //调用B方法，枚举出不同的第一行 if(FirstRow()){ // 输出所得到的数组 for(int i=1;i<press.length;i++){ //行 for(int j=1;j<press[i].length-1;j++){ //列 System.out.print(press[i][j]+" "); } System.out.println(); //换行 } }else{ System.out.println("找不到解法"); }}//首行随机数方法static boolean FirstRow(){//B//二进制转换器 for(int i=0;i<light.length;i++){ //行 for(int j=0;j<light[i].length;j++){ //列 press[i][j]=0; //初始化所有按钮为0，包括外围 } }//调用C方法，把枚举值传过去，根据返回结果，更换第一行 while(!guess(press)){ //执行结果不正确时 press[1][1]++; int c=1; //指向的数 while(press[1][c]>1){ //检验进位器:从第一位开始检查，一大于1就进一位 press[1][c]=0; c++; press[1][c]++; if(press[1][press[1].length-2]>1){ //说明都超位了还找不到 return false; //找不到了 } } } return true; //找到了按钮}static boolean guess(int press[][]) { //C //通过第一行获取其他行的操作情况 for(int i=2;i<press.length;i++){ //从第二列到最后一列 for(int j=1;j<press[i].length-1;j++){ //该列的每一项 press[i][j]=(light[i-1][j]+press[i-1][j]+press[i-1][j-1]+press[i-1][j+1]+press[i-2][j])%2; //该项的按钮操作情况取决于上个按钮操作后的情况 } } //验证最后一行与与灯亮的关系是否为灯灭，返回结果 for(int i=1;i<press[press.length-1].length-1;i++){ if((press[press.length-1][i]+press[press.length-1][i-1]+press[press.length-1][i+1]+press[press.length-2][i])%2!=light[press.length-1][i]){ //不相等说明最后亮 return false; } } return true;}}3.讨厌的青蛙1.题目1.直线路径：每只青蛙总是沿着一条直线跳跃稻田2.相同间距：且每次跳跃的距离都相同3.有进有出：而青蛙总是从稻田的一侧跳进稻田, 然后沿着某条直线穿 越稻田, 从另一侧跳出去4.多项干扰：可能会有多只青蛙从稻田穿越
.png)
问题： 在各条青蛙行走路径中, 踩踏水稻最多的那一条上, 有多 少颗水稻被踩踏2.解题1.输入 6 7 //6行7列 14 //被踩的数量14棵 2 1 //稻子的坐标 3 4 5 3... （总共14个）2.输出 7 （单只青蛙踩最多的步数，没有输出为0）3.分析 第一想法：枚举每一条路径的情况， 起点可能性*方向可能性*步长可能性=非常多（不可取）当我们确定的想法为前两个的时候，我们就可以确定步长，步长有两个，dX是X方向上，dY是Y方向上。确定了步长就可以减少：1.前面需要超过稻田 2.后面没有超过稻田 第二想法：枚举两个点的组合，判断这两个点能不能成立。成立的话计算最多步数。首先获取行列，稻子坐标，然后排序稻子大小，排序方式我本来是想用ArrayList来存坐标对象，但是这样做得手动进行位置交换，所以我就想到用TreeSet的方式，这样就可以自动排序。接下来就对稻子进行一一组合，组合后有一些组合根本就不能存在，像第一步前一步如果在稻田里的话（需要判断XY，continue掉），还有就是设立最大步数（初始化为2），如果（最大步数-1）步的时候到了稻田外（需要判断两个，X判断break，Y判断continue，因为包含的关系），那也不行。调用步长方法：从这点触发，传dX，dY，能够走几步，将返回的步数赋给最多步最后判断最多步如果为2，则归为0步长方法添加步长，添加步数做while循环，做判断坐标没有越界，就不断添加步数4.小结思路A获取行列数，被踩数量，稻子坐标（坐标用对象的方式实现，新建一个类）调用B方法，排序稻子坐标循环x，y坐标，一个个组合，判断组合如果符合条件 当第一步减去步长大于1 大于1与小于稻田长宽，跳过这次循环 当第一步X+最大步数（-1）*步长如果越界，跳过整个循环 当第一步Y+最大步数（-1）*步长如果越界，跳过这次循环（因为属于子类）调用C方法，获取最大步数判断最大步数为2，则归为0BX从小到大，Y从小到大C初始化步数为2，第一步变为第二步（XY）做while循环，当变化后的xy没有超过稻田，就不断把步数加上去最终返回最大步数5.代码实现package Test;import java.util.ArrayList;import java.util.Iterator;import java.util.Scanner;import java.util.TreeSet;public class Test { static int c; static int r; static ArrayList<Sign> al; public static void main(String[] args) { int max=2; //定义最大步数为2// A// 获取行列数，被踩数量，稻子坐标（坐标用对象的方式实现，新建一个类） System.out.println("请输入行，列，被踩稻子数："); @SuppressWarnings("resource") Scanner input=new Scanner(System.in); r=input.nextInt(); c=input.nextInt(); int desNum=input.nextInt(); //被踩稻子数 System.out.println("请输入被踩稻子的坐标："); //记录稻子坐标 TreeSet<Sign> ts=new TreeSet<Sign>(); //用TreeSet的自动排序 for(int i=0;i<desNum;i++){ ts.add(new Sign(input.nextInt(), input.nextInt())); //y&x } al=new ArrayList<Sign>(); //将TreeSet转存到ArrayList Iterator<Sign> it=ts.iterator(); while(it.hasNext()){ al.add(it.next()); }// 循环坐标，一个个组合，判断组合如果符合条件 for(int i=0;i<al.size();i++){ for(int j=i+1;j<al.size();j++){ //组合跟顺序无关，所以用i+1 int dX=al.get(j).x-al.get(i).x; //xd:x的跨距，后面的减前面的 int dY=al.get(j).y-al.get(i).y; int pX=al.get(i).x-dX; //得到第一步的前一步，用于验证 int pY=al.get(i).y-dY;// 当第一步减去步长大于1 大于1与小于稻田长宽，跳过这次循环 if(pX>=1&&pY>=1){ //前一步在田里面 continue; //跳过这一次循环 }// 当第一步X+最大步数（-1）*步长如果越界，跳过整个循环 if(al.get(i).x+(max-1)*dX>r){ //判断如果加上最大步就超过田，跳过循环i break; }// 当第一步Y+最大步数（-1）*步长如果越界，跳过这次循环（因为属于子类） if(al.get(i).y+(max-1)*dY>c){ continue; }// 调用B方法，获取最大步数 int step=Step(al.get(i),dX,dY); if(step>max){ //步数超过的记录起来 max=step; } } }// 判断最大步数为2，则归为0 if(max==2){ max=0; } System.out.println(max); }//获取最大步数 private static int Step(Sign step,int dX,int dY){// B// 做while循环，当变化后的xy没有超过稻田，就不断把步数加上去 int max=0; int x=step.x; //不能用对象，对象只是地址符，重量级 int y=step.y; while(x<=c&&y<=r){ //判断没有超出田地时,可以等于田地。注意边缘数据 //判断是不是踩倒的稻草 if(!isDao(y,x)){ //新产生的对象不能和旧的比较 max=0; break; } x+=dX; y+=dY; max++; //加1次就多一步，但是最后一次是在田外的，所以抵消第一步 }// 最终返回最大步数 return max; }//判断是不是踩倒 private static boolean isDao(int y,int x){ boolean flag=false; for(int i=0;i<al.size();i++){ if(al.get(i).y==y){ if(al.get(i).x==x){ flag=true; } } } return flag; }}//新建坐标类class Sign implements Comparable<Sign>{ //继承Comparable对数据进行比较 int x; int y; Sign(int y,int x) { //构造方法赋值 this.x=x; this.y=y; } @Override //定义排序规则 public int compareTo(Sign o) { if(this.x>o.x){ return 1; }else if(this.x<o.x){ return -1; }else{ if(this.y>o.y){ return 1; }else if(this.y<o.y){ return -1; }else{ return 0; } } }}资料来自：https://www.coursera.org/learn/suanfa-jichu/lecture/rfoj5/mei-ju-de-ji-ben-si-xiang新闻热点
疑难解答
