计算九宫格解锁的解法和

爱被打了一巴掌 2022-06-18 10:18 209阅读 0赞

**要求：**

> 至少经过四个点；  
> 不能重复经过同一个点；  
> 路径上的中间点不能跳过（如从1到3一定会经过2）；  
> 如果中间的点是之前已经用过的，那么这个点就可以被跳过（如213，因为2已经被用过，1就可以越过2与3连接，132是不允许的）。

**输出**

> 九宫格的解法和（一个数字）

**代码**

public class Main { 
       static int[][] a= new int[10][10];
       public static void main(String[] args) {
          //排除不可能情况
          a[1][3] = 2;
          a[3][1] = 2;
          a[4][6] = 5;
          a[6][4] = 5;
          a[7][9] = 8;
          a[9][7] = 8;
          a[1][7] = 4;
          a[7][1] = 4;
          a[2][8] = 5;
          a[8][2] = 5;
          a[3][9] = 6;
          a[9][3] = 6;
          a[1][9] = 5;
          a[9][1] = 5;
          a[3][7] = 5;
          a[7][3] = 5;
          //计算长度为2~9的解法和
          System.out.println(f(4,"")+f(5,"")+f(6,"")+f(7,"")+f(8,"")+f(9,""));//389112
       }
       private static int f(int tar, String result) {
           int sum = 0;//解法和
           //当长度为0时，返回1
           if(tar == 0)
               return 1;
           for(int i = 1;i <= 9;i++){
               //当序列中存在i，则跳过
               if(result.contains(i+""))
                        continue;
               //当序列非空时逻辑
               if(result.length() > 0){
                   //找到序列中最后的起点
                   int x = result.charAt(result.length()-1) - '0';
                   //当起点到i不能直达(a[x][i]>0)且结果中不存在中间点(a[x][i])，跳过
                   if(a[x][i] > 0 && !result.contains(a[x][i]+""))
                       continue;
               }
               //递归求和
               sum += f(tar-1,result+i);
           }
           return sum;
       }  
    }