手机屏幕解锁模式

import java.util.*;

/*
        图形密码即使图案相同，但是顺序不同的话也算作一种
        dfs，以每个位置作为起点，然后走 [n, m] 个点
        当走到无路可走的时候，如果走的点小于 m，那么该路径不满足要求
        当已经走的点 > n 的时候，那么表示接下来的路径也不满足要求，直接返回
        
        当我们发现周围 几个点都已经走过了，如果是普通的 dfs，这时候已经返回了
        但是，我们可以越过已经访问过的点，继续往下一个点走，因此我们需要判断
        8 个方向第 2 个点是否已经访问过了，如果没有，那么可以继续访问
        
        注意：只有我们发现某个方向上的点访问过了才可以越过该点
        如果该方向上的第一个点还没有访问，那么我们不能直接越过
        */
public class Solution {
    /**
     * 实现方案
     * @param m int整型 最少m个键
     * @param n int整型 最多n个键
     * @return int整型
     */
    public int solution (int m, int n) {
        //范围处理
        if(m > n){
            return 0;
        }
        m = Math.max(0, m);
        n = Math.min(9, n);
        if(n == 0){
            return 0;
        }
        // write code here
        res = 0;
        visited = new boolean[3][3];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                dfs(i, j, m, n, 1);
            }
        }
        return res;
    }
    static int res;
    static boolean[][] visited;
    int[][] pos = {
            {1, 0},{1, 1},{1, -1}, {-1, 0}, {-1, -1}, {-1, 1}, {0, 1}, {0, -1},
            {1, 2}, {2, 1}, {-1, 2}, {-1, -2}, {-2, -1}, {-2, 1}, {1, -2}, {2, -1}
    };
    private void dfs(int i, int j, int m, int n, int p){
        if(p >= m){
            res++;
        }
        //当访问个数大于等于 n 个，那么已经足够了，无需继续访问
        if(p >= n){
            return;
        }

        visited[i][j] = true;
        //8 个方向走一遍
        for(int[] po : pos){
            int x = i + po[0];
            int y = j + po[1];
            if(!isEvil(x, y)){
                if(!visited[x][y]){
                    dfs(x, y, m, n, p + 1);
                }else{
                    //越过同方向上的点
                    int xx = x + po[0];
                    int yy = y + po[1];
                    if(!isEvil(xx, yy) && !visited[xx][yy]){
                        //越过 (x, y) 点，访问下一个点
                        dfs(xx, yy, m, n, p + 1);
                    }
                }
            }
        }
        visited[i][j] = false;
    }
    private boolean isEvil(int i, int j){
        return i < 0 || i >= 3 || j < 0 || j >= 3;
    }
}

公众号“乘风破浪Now”更多内容可查看

分析

这道题与一般的回溯的题目不太一样，这道题的难点在于下一个点可以不是与当前点相邻。这道题回溯的下探规则不能是一个点的相邻点（正上方/正下方/正左方/正右方/左上方/左下方/右上方/右下方）。因为这道题的下探点可以是矩形对角处。如何确定下探规则成为了解这道题的关键，这个下探规则需要适用于所有的点。

现在来确定下探规则：将下探规则分为16个方向前8个用于下探相邻的点，后8个用于下探矩形对角的点。若在 A 方向上下探相邻的点发现该点已经走过，则再在 A 方向上再走多一步则可以下探到与当前点不相邻的点。（A方向为前8个常规方向）

以上下探规则对所有点均适用。

static int[][] directs = 
{{-1,1},{0,1},{1,1},{-1,0},{1,0},{-1,-1},{0,-1},
{1,-1},{2,-1},{1,-2},{-2,-1},{-1,-2},{1,2},{2,1},{-2,1},{-1,2}};

代码

public class Question64 {
    static int[][] directs = {{-1,1},{0,1},{1,1},{-1,0},{1,0},{-1,-1},{0,-1},{1,-1},
            {2,-1},{1,-2},{-2,-1},{-1,-2},{1,2},{2,1},{-2,1},{-1,2}};

    static int[][] dash = { {1,2,3},
                            {4,5,6},
                            {7,8,9}};

    static int[] nums = new int[10];

    static public int solution(int m,int n){
        m = m<=9 ? m : 9;
        n = n<=9 ? n : 9;
        int sum=0;
        int[] nums ={0, 9, 56, 320, 1624, 7152, 26016, 72912, 140704, 140704 };
        for (int i=m;i<=n;i++){
            sum += nums[i];
        }
        return sum;
    }

    static public void process(boolean[] V,int count,int x,int y){
        if(count==9){
            nums[count]++;
            return;
        }
        V[dash[x][y]]=true;
        nums[count]++;

        for(int i=0;i<directs.length;i++){
            int a= x+directs[i][0];
            int b= y+directs[i][1];
            if(canVisit(V,a,b)){
                process(V,count+1,a,b);
            }else if(i<8){ // 若是常规方向，则再多走一步则可以走到与当前点不相邻的点
                a +=directs[i][0];
                b +=directs[i][1];
                if(canVisit(V,a,b)){
                    process(V,count+1,a,b);
                }
            }
        }
        V[dash[x][y]]=false;
    }

    static boolean canVisit(boolean[] V,int i,int j){
        if(i<0 || i>=3 || j<0 || j>=3 || V[dash[i][j]]) return false;
        return true;
    }

    public static void main(String[] args) {
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                process(new boolean[10],1,i,j);
            }
        }

        for (int num : nums) {
            System.out.print(num+" ");
        }
    }
}

//提交时间：2020-04-29 语言：C++ 运行时间： 50 ms 占用内存：504K 状态：答案正确
class Solution {
 public:
  bool check(int i, int j) {
    if ((i >= 0 && i <= 2) && (j >= 0 && j <= 2) && !isVisit(i, j)) {
      return true;
    }
    return false;
  }
  bool isVisit(int i, int j) { return visited[i][j] == 0 ? false : true; }
  int visited[5][5] = {0};
  int map[16][2] = {{-1, 0}, {-1, 1},  {0, 1},   {1, 1},  {1, 0}, {1, -1},
                    {0, -1}, {-1, -1}, {-2, 1},  {-1, 2}, {1, 2}, {2, 1},
                    {2, -1}, {1, -2},  {-1, -2}, {-2, -1}};
  int dfs(int i, int j, int depth) {
    if (depth == 1) {
      return 1;
    } else if (depth == 0) {
      return 0;
    }
    int num = 0;
    visited[i][j] = 1;
    for (int k = 0; k < 16; k++) {
      int pi = i + map[k][0];
      int pj = j + map[k][1];
      if (check(pi, pj)) {
        num += dfs(pi, pj, depth - 1);
      } else if (k < 8) {
        pi += map[k][0];
        pj += map[k][1];
        if (check(pi, pj)) {
          num += dfs(pi, pj, depth - 1);
        }
      }
    }
    visited[i][j] = 0;
    return num;
  }
  /**
   * 实现方案
   * @param m int整型 最少m个键
   * @param n int整型 最多n个键
   * @return int整型
   */
  int solution(int m, int n) {
    int count = 0;
    m = m >= 0 && m <= 9 ? m : 0;
    n = n >= 0 && n <= 9 ? n : 9;
    for (; m <= n; m++) {
      for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
          count += dfs(i, j, m);
        }
      }
    }
    return count;
  }
};

import java.util.*;


public class Solution {
    /**
     * 实现方案
     * @param m int整型 最少m个键
     * @param n int整型 最多n个键
     * @return int整型
     */
    private int[][] direction = new int[][]{
            {0,1},{0,-1},{-1,0},{1,0},
            {1,1},{1,-1},{-1,1},{-1,-1},
            {1,-2},{1,2},{-1,2},{-1,-2},
            {2,-1},{2,1},{-2,-1},{-2,1}};    //方向数组
    private int[] arr;    //结果数组，每个arr[i]存的是i个操作形成的模式数量
    private int n;        //输入的n，全局化，不用传参
    public int solution (int m, int n) {
        // write code here
        arr = new int[n+1];
        this.n = n;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                boolean hasVisited[][] = new boolean[3][3];  //是否访问过当前元素
                hasVisited[i][j] = true;
                dfs(i,j,1,hasVisited);
            }
        }
        int ret = 0;
        for(int i=m;i<=n;i++){
            ret+=arr[i];
        }
        return ret;
    }
    private void dfs(int i, int j, int count, boolean [][] visited){
        if(count>n){
            return;
        }
        arr[count]++;
        for(int[] d:direction){
            int x = i +d[0];
            int y = j +d[1];
            if(x>=0&&x<3&&y>=0&&y<3){
                if(!visited[x][y]){
                    visited[x][y] = true;
                    dfs(x,y,count+1,visited);
                    visited[x][y] = false;
                }else{
                    int nX = x+d[0];     //夸过已访问的中间的值访问隔壁的值，隔山打牛
                    int nY = y+d[1];
                    if(nX>=0&&nX<3&&nY>=0&&nY<3&&!visited[nX][nY]){
                        visited[nX][nY] = true;
                        dfs(nX,nY,count+1,visited);
                        visited[nX][nY] = false;
                    }
                }

            }
        }

    }
}

class Solution {
public:
    /**
     * 实现方案
     * @param m int整型 最少m个键
     * @param n int整型 最多n个键
     * @return int整型
     */
    int solution(int m, int n) {
        vector<bool> vis(9);
        return 4 * (dfs(0, 1,vis, m, n) + dfs(1, 1,vis, m, n)) + dfs(4, 1,vis,m,n);
    }
  
    int dfs(int i, int cnt, vector<bool> vis, int m, int n) {
        if (cnt > n) return 0;
        int res = cnt >= m ? 1 : 0;
        vis[i] = true;
        int x = i / 3, y = i % 3;
        for (int j = 0; j < 9; ++j) {
            if (vis[j]) continue;
            int xx = j / 3, yy = j % 3;
            int dx = abs(x - xx), dy = abs(y - yy);
            int a = min(dx, dy), b = max(dx, dy);
            if (b <= 1 || a == 1 && b == 2) {
                res += dfs(j, cnt + 1, vis, m, n);
            }
            else {
                int xmid = (x + xx) / 2, ymid = (y + yy) / 2;
                if (vis[xmid * 3 + ymid]) res += dfs(j, cnt + 1, vis, m, n);
            }
        }
        return res;
    }
};

#打个表通过
class Solution:
    def solution(self , m , n ):
        # write code here
        candi = [0,9, 56, 320, 1624, 7152, 26016, 72912, 140704, 140704]
        res = 0
        for i in range(m, n+1):
            if i == 0: continue
            if i>9: break
            res += candi[i]
        return res

class Solution:
    def solution(self , m , n ):
        # write code here
        res = 0
        for i in range(m, n+1):
            if i==0:continue
            res += self.compute(i)
        return res
    def compute(self, k):
        self.cnt = 0
        board = [['.']*3 for _ in range(3)]
        self.x = -1
        self.y = -1
        
        def isValid(board, row, col):
            if self.x == -1 and self.y == -1:
                return True
            if abs(row-self.x) > 1 and col == self.y:
                if board[(row+self.x)//2][col] != 'Q':
                    return False
            elif abs(col-self.y) > 1 and row == self.x:
                if board[row][(col+self.y)//2] != 'Q':
                    return False
            elif abs(col-self.y) > 1 and abs(row-self.x) > 1:
                if board[(row+self.x)//2][(col+self.y)//2] != 'Q':
                    return False
            return True
        
        
        def trackback(board, k, path):
            if k==0: 
                self.cnt += 1
                self.x, self.y = path[-2]
                return
            for i in range(3):
                for j in range(3):
                    if board[i][j] == 'Q': continue
                    if not isValid(board, i, j): continue
                    board[i][j] = 'Q'
                    path.append((i,j))
                    self.x, self.y = i, j
                    trackback(board, k-1, path)
                    self.x, self.y = path[-2]
                    path.pop()
                    board[i][j] = '.'
    
        trackback(board, k, [(-1,-1)])
        return self.cnt

# 实现方案: DFS
# 编码方案：[1 2 3
#          4 5 6
#          7 8 9]
#
class Solution:
    def solution(self, m, n):
        if m > n or n <= 0:
            return 0
        
        # 边界修正（还能有[3, 20]这种测试也是醉了）
        if m <= 0:
            m = 1
        if n > 9:
            n = 9
        
        # 初始数据：保存1-9长度路径和，原始结点的set，当前所有路径
        ret = [9]
        oriSet = set(range(1, 10))
        currList = [[1], [2], [3], [4], [5], [6], [7], [8], [9]]
          
        for _ in range(2, n + 1):
            nextList = []
            for currline in currList:
                for i in (oriSet - set(currline)):
                    if self.isValid(currline, i):
                        tmp = currline[:] + [i]
                        nextList.append(tmp)
            currList = nextList
            ret.append(len(currList))
          
        return sum(ret[m-1:n])
    
    def isValid(self, currline, i):
        # 判断currline能否增加i这个结点
        # 此时为空，或者中点不是整数
        if currline == [] or (currline[-1] + i) % 2 == 1:
            return True
          
        # 此时mid必然是整数
        mid = (currline[-1] + i) // 2
        midList = [{1, 3}, {4, 6}, {7, 9}, {1, 7}, {2, 8}, {3, 9}, {1, 9}, {3, 7}]
          
        if mid in currline&nbs***bsp;set([currline[-1], i]) not in midList:
            return True
        else:
            return False

# Python3 dfs
# 所有方向
di = [(1,0), (-1,0), (0,1), (0,-1), (1,1), (-1,-1), (1,-1), (-1,1), (1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1),(-2,1),(-2,-1)]
# 可跨一个点的方向
ds = [(1,0), (-1,0), (0,1), (0,-1), (1,1), (-1,-1), (1,-1), (-1,1)]
# 9个点
nodes = {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)}
def dfs(x, y, visited, count):
    visited.add((x, y))
    count -= 1
    ans = 0
    if count == 0:
        ans += 1
    else:
        for d in di:
            if (x+d[0], y+d[1]) in visited or (x+d[0], y+d[1]) not in nodes:
                if d not in ds:
                    continue
                else:
                    dx = d[0] * 2
                    dy = d[1] * 2
                    if (x+dx, y+dy) in nodes and (x+dx, y+dy) not in visited:
                        ans += dfs(x+dx, y+dy, visited, count)                       
            else:
                ans += dfs(x+d[0], y+d[1], visited, count)
    visited.remove((x, y))
    return ans

ans = [0] * 10
for count in range(1, 10):
    for i in range(3):
        for j in range(3):
            visited = set()
            ans[count] += dfs(i, j, visited, count)
# ans[i]即为i个键的结果数
# ans = [0, 9, 56, 320, 1624, 7152, 26016, 72912, 140704, 140704]
print(ans)
 

class Solution {
public:
    void move(vector<vector<int> >& board, int i, int j, int k, int m, int n, int& ans){
        // 如果已经走过的点数大于等于m，则是有效路径，ans++
        if(k >= m) ans ++;
        // 如果已经走过的点数等于n，则不需要继续探索，故返回
        if(k == n) return;
        // 如果已经走过的点数小于n，则还可以继续探索
        for(int dx=-2; dx<=2; dx++){
            for(int dy=-2; dy<=2; dy++){
                if(i+dx>=0 && i+dx<=2 && j+dy>=0 && j+dy<=2 && board[i+dx][j+dy]==0){
                    // 如果两点之间没有第三个点（条件：dx%2 || dy%2），则无需判断是否经过“已经过”的点
                    // 如果两点之间有第三个点，则需要判断这个点是否是已经走过的点
                    if(dx%2 || dy%2 || (!(dx%2) && !(dy%2) && board[i+dx/2][j+dy/2]==1)){
                        board[i+dx][j+dy] = 1;
                        move(board, i+dx, j+dy, k+1, m, n, ans);
                        board[i+dx][j+dy] = 0;
                    }
                }
            }
        }
         
        return;
    }
     
    int solution(int m, int n) {
        // write code here
        vector<vector<int> > board(3, vector<int>(3, 0));
        int ans = 0;
        // 如果n等于0，则直接返回0
        if(n == 0) return ans;
        
        // 选择棋盘上任意一点作为起点
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                board[i][j] = 1;
                move(board, i, j, 1, m, n, ans);
                board[i][j] = 0;
            }
        }
        return ans;
    }
};

Java版本，比较容易想到，但是调试了很多遍。

public static int solution (int m, int n) {
//         递归实现
         int count = 0;
         n = n>9 ? 9 : n;
         for(int i=m;i<=n;i++) {
             boolean[][] flags = new boolean[3][3];
             for(int j=0;j<3;j++) {
                 for(int t=0;t<3;t++) {
                     count += findNext(flags, j, t, 0, i);
                 }
             }
         }
         return count;
     }

     public static int findNext(boolean[][] flags,int curRow, int curCol, int steps, int n) {
         int count = 0;
         steps ++;
         flags[curRow][curCol] = true;
//         步数走完返回
         if(steps == n)
             return 1;
//         如果可以走，那么返回 1
         for(int i=0;i<3;i++) {
             for(int j=0;j<3;j++) {
                 if(flags[i][j] == false && canStep(flags, curRow, curCol, i, j)) {
                     count += findNext(flags, i, j, steps, n);
//                     恢复状态
                     flags[i][j] = false;
                 }
             }
         }
         flags[curRow][curCol] = false;
         return count;
     }

     public static boolean canStep(boolean[][] flags, int curRow, int curCol, int targetRow, int targetCol) {
//         在同一行
         if(curRow == targetRow) {
             int low = curCol < targetCol?curCol:targetCol;
             if(Math.abs(curCol - targetCol) >1 && flags[curRow][low+1] == false)
                 return false;
         }
//         在同一列
         if(curCol == targetCol) {
             int low = curRow < targetRow?curRow:targetRow;
             if(Math.abs(curRow - targetRow) >1 && flags[low+1][curCol] == false)
                 return false;
         }
//         斜对角
         if(Math.abs(curRow-targetRow)==2 && Math.abs(curCol-targetCol)==2 && flags[1][1] == false)
             return false;
         return true;
     }

1、Python3技巧：使用itertools.permutations生成所有可能路径，逐个检查是否可行
2、路径是否可行，取决于相邻两个点的连线之间是否出现还没有经过的点，例如，如果没有先经过点2，那么不能出现连线(1, 3)
3、路径存在镜像对称性，可以节省大量的搜索过程，比如以3、7、9开头的路径可以对称到以1开头的路径，同理以4、6、8开头的路径可以对称到以2开头的路径。

from itertools import permutations

class Solution:
    def solution(self, m, n):
        if n == 0: return 0
        if m == 0: m = 1
        e = {(1, 3), (4, 6), (7, 9),
             (1, 7), (2, 8), (3, 9),
             (1, 9), (3, 7)}
        h, c = {3, 4, 6, 7, 8, 9}, 0
        for k in range(m, n + 1):
            for a in permutations(range(1, 10), k):
                if a[0] in h: continue
                t = set()
                for i in range(len(a) - 1):
                    if (a[i], a[i+1]) in e or (a[i+1], a[i]) in e:
                        if (a[i] + a[i+1]) // 2 not in t: break
                    t.add(a[i])
                else: c += 1 if a[0] == 5 else 4
        return c

可以知道的是共有24个可能的合法方向
所以将这24个防向预处理出来放在数组中
对于后8个方向，需要判断被跳过的格子有没有被访问过
剩下的dfs解决就好了

int x[] = {0, -1, 0, 1, -1, 1, 1, -1, 2, 2, -2, -2, 1, 1, -1, -1, 2, -2, 2, -2, 2, -2, 0, 0};
int y[] = {1, 0, -1, 0, -1, 1, -1, 1, 1, -1, 1, -1, -2, 2, -2, 2, 2, -2, -2, 2, 0, 0, 2, -2};
class Solution {
public:
    /**
     * 实现方案
     * @param m int整型 最少m个键
     * @param n int整型 最多n个键
     * @return int整型
     */
    bool vis[4][4];
    int _n, _m;
    int ans = 0;
    bool valid(int x, int y){
        return x>=0 && x<3 && y>=0 && y<3 && !vis[x][y];
    }
    void dfs(int row, int col, int cnt){
        if(cnt > _m)
              return;
        if(cnt >= _n && cnt <= _m)
            ans += 1;
        for(int i = 0; i < 24; i++){
            int tempx = row + x[i];
            int tempy = col + y[i];
            if(valid(tempx, tempy)){
                if(i >= 16){
                    int helpx = x[i]/2;
                    int helpy = y[i]/2;
                    if(!vis[row + helpx][col + helpy]){
                        continue;
                    }
                }
                vis[tempx][tempy] = true;
                dfs(tempx, tempy, cnt + 1);
                vis[tempx][tempy] = false;
            }
        }

    }
    int solution(int m, int n) {
        // write code here
        _n = m;
        _m= n;
        ans = 0;
        memset(vis, 0 , sizeof vis);
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                memset(vis, 0, sizeof vis);
                vis[i][j] = true;
                dfs(i, j, 1);
            }
        }
        return ans;
    }
};

class Solution {
public:
    bool matrix[3][3] = {{false, false,false} , 
                         {false, false,false} , 
                         {false, false,false} };
    int m, n;
    int res = 0;
    int solution(int m, int n) {
        // 深度为m到n，深度优先遍历，记录搜索时的深度
        res = 0;
        this->m = m <= 0 ? 1 : m;
        this->n = n > 9 ? 9 : n;
        if (this->m < 1 || this->n < m)
            return 0;
        int length = 0;
        for (int i = 0; i <= 2; ++i)
            for (int j = 0; j <= 2; ++j) {
                dfs(length, i, j);
            }
        return res;
    }
    void dfs(int& length,int i, int j)
    {
        if (length >= n)
            return;
        matrix[i][j] = true;
        length++;
        if (length >= m && length <= n)
            res++;
        for (int x = 0; x <= 2; ++x)
            for (int y = 0; y <= 2; ++y) {
                if (length < n && isVaild(i, j, x, y))
                    dfs(length, x, y);
            }
        length--;
        matrix[i][j] = false;
        return;
    }
    bool isVaild(int i, int j, int x, int y)
    {
        if (x < 0 || y > 2 || x < 0 || y > 2)
            return false;
        if (matrix[x][y] == true)
            return false;
        int midI = (i + x) / 2;
        int midJ = (j + y) / 2;
        if ((abs(x - i) == 0 && abs(y - j) == 2)
            || (abs(x - i) == 2 && abs(y - j) == 0)
            || (abs(x - i) == 2 && abs(y - j) == 2)) {
            if (matrix[midI][midJ] == false)
                return false;
        }
        return true;
    }
};