python123九宫格输入法_手机屏幕解锁模式

36

可以通过DFS的方式先计算出刚好按下n个键时有多少种组合，然后求出S[n]至S[M]的和。

DFS的主要难度在于，下一步可以与当前的位置不直接相连。这时分两种情况：

1. 普通的八个方向 (上下左右以及其45度夹角方向)：

若这八个方向都已经越界或走过了，则这时无路可走。若是普通的DFS则返回，但是九宫格解锁可以跳过相邻的一格。注意只能在这八个方向跳多一步，相当于踩着已经被按下的位置再沿着相同方向走一步。

2.其余的八个方向

其余的八个方向虽然不直接与当前位置直接相连，但是它与当前位置的连线不会触碰到其他位置，因此也可以直接到达。

以下为DFS代码

int dir[16][2] = {//16个方向

{ -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 isVisit[5][5];//是否已按下

bool canVisit(int i, int j){//判断能否按下

if (i 3 || j 3 || isVisit[i][j]) return false;

return true;

}

int times[10];

//d:已经被选中的键的个数(深度)

void DFS(int i, int j, int d){

if (d == 9){

return;

}

isVisit[i][j] = true;

times[d++] ++;

//选择下一个键

for (int y = 0; y 

int ni = i + dir[y][0], nj = j + dir[y][1];

if (canVisit(ni, nj)){//该点未被选择

DFS(ni, nj, d);

}

else if (y 

ni += dir[y][0];

nj += dir[y][1];

if (canVisit(ni, nj) ){//该点未被选择

DFS(ni, nj, d);

}

}

}

isVisit[i][j] = false;

return;

} solution：

class Solution {

public:

int solution(int m, int n) {

if(m > n){    //易被忽略

return 0;

}

m = (m<0? 0: m);    //参数检查必须有

n = (n>9? 9:n);

int tmp[] = {0, 9, 56, 320, 1624, 7152, 26016, 72912, 140704, 140704 };

int ans = 0;

for(int i=m; i<=n; i++){

ans += tmp[i];

}

return ans;

}

};

发表于 2020-04-01 21:43:16

回复(5)

12

# 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)

编辑于 2020-04-02 18:52:08

回复(2)

7

class Solution {

public:

void move(vector >& 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 > board(3, vector(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;

}

};

发表于 2020-04-21 19:06:47

回复(2)

4

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;

}

发表于 2020-04-24 12:58:52

回复(5)

2

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 

for(int j = 0; 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 = 3 || j = 3;

}

}

发表于 2020-08-12 14:07:07

回复(0)

2

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

发表于 2020-06-05 20:00:17

回复(1)

2

公众号“乘风破浪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

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-05-31 21:11:35

回复(0)

2

//提交时间：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 

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 

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 

for (int j = 0; j 

count += dfs(i, j, m);

}

}

}

return count;

}

};

发表于 2020-04-29 14:46:44

回复(0)

1

class Solution {

public:

/**

* 实现方案

* @param m int整型 最少m个键

* @param n int整型 最多n个键

* @return int整型

*/

int solution(int m, int n) {

vector 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 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 

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;

}

};

发表于 2020-09-02 12:40:35

回复(0)

1

#打个表通过

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

正经答案：(简单易懂DFS，时间超了，通过80%)

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

供你们参考，和leetcode上面的N皇后思路差不多，DFS+剪枝

发表于 2020-06-07 00:22:18

回复(0)

1

# 实现方案: 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

编辑于 2020-06-05 10:05:19

回复(0)

1

本来以为有什么规律，结果浪费了很多时间，没想到还是暴力DFS 就是剪枝有点麻烦

提交时间：2020-05-08 语言：Java 运行时间： 101 ms 占用内存：13312K 状态：答案正确

import java.util.*;

public class Solution {

/**

* 实现方案

* @param m int整型 最少m个键

* @param n int整型 最多n个键

* @return int整型

*/

private int sum = 0;

public int solution (int m, int n) {

if (m <= n) helper(new boolean[9], 0, m, n, -1);

return sum;

}

private void helper(boolean[] hash, int num, int m, int n, int curr) {

if (num == n) return;

for (int i = 0; i 

if (hash[i] || isCorr(hash, curr, i)) continue;

hash[i] = true;

if (num + 1 >= m) sum++;

helper(hash, num + 1, m, n, i);

hash[i] = false;

}

}

private boolean isCorr(boolean[] hash, int i, int j) {

if (i == -1) return false;

if (i > j) return isCorr(hash, j, i);

if (i == 0) {

if (j == 2 && !hash[1]) return true;

if (j == 6 && !hash[3]) return true;

if (j == 8 && !hash[4]) return true;

}

if (i == 2) {

if (j == 6 && !hash[4]) return true;

if (j == 8 && !hash[5]) return true;

}

if (i == 6 && j == 8 && !hash[7]) return true;

if (i + j == 8 && !hash[4]) return true;

return false;

}

}

发表于 2020-05-08 22:05:29

回复(0)

2

有人跟我一样想用Java的吗

发表于 2020-04-03 20:45:40

回复(1)

0

public  int solution (int m, int n) {

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

//递归实现

int count = 0;

if(n

return 0;

}

if(m==0){

m=1;

}

n = n > 9 ? 9:n;

for(int i= m ;i <= n;i++){

for(int j=0;j<3;j++){

for(int k=0;k<3;k++){

List list = new ArrayList<>();

list.add(arr[j][k]);

count += findNext(list,arr,j,k,1,i);

}

}

}

return count;

}

public  int findNext(List list,int[][] arr,int j,int k,int step,int stepCount){

if(step >= stepCount){

//System.out.println(list);

return 1;

}

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

int count = 0;

//上一步

for(int i= 0;i<3;i++){

for(int z=0;z<3;z++){

int s = step;

int lastStep = arr[j][k];

if(!list.contains(arr[i][z])){

boolean flag = true;

for(int r=0;r<8;r++){

//当之前的步骤中存在 则可以绘制

if(((b[r][0] == lastStep && arr[i][z] == b[r][1]) || (b[r][1] == lastStep && arr[i][z] == b[r][0])) && !list.contains(b[r][2])){

flag = false;

}

}

if(flag){

s ++;

List integers = new ArrayList<>(list);

integers.add(arr[i][z]);

//System.out.println(integers);

count+=  findNext(integers,arr,i,z,s,stepCount);

}

}

}

}

return count;

}

发表于 2020-09-25 15:36:29

回复(2)

0

将九宫格的九个格子当做0-8

如,  0,1,2

3,4,5

6,7,8

数组 d[i][j] = n 的意思是：如果当前格是i，下一格选择j，是否经过了某格，如果是0则说明没有经过任何格子，不为0则是经过的格子n， 比如d[0][6] = 3，说明从0到6需要经过3。

数组sign保存了某个数字是否已经被选择，所以在 i 格 选择 j 格为下一格需要经过 n 格， 只要判断 sign [ n ] 是否已经被选择。

class Solution {

public:

/**

* 实现方案

* @param m int整型 最少m个键

* @param n int整型 最多n个键

* @return int整型

*/

vector> d = {

{0,0,1,0,0,0,3,0,4},

{0,0,0,0,0,0,0,4,0},

{1,0,0,0,0,0,4,0,5},

{0,0,0,0,0,4,0,0,0},

{0,0,0,0,0,0,0,0,0},

{0,0,0,4,0,0,0,0,0},

{3,0,4,0,0,0,0,0,7},

{0,4,0,0,0,0,0,0,0},

{4,0,5,0,0,0,7,0,0}

};

int ans = 0;

int solution(int m, int n) {

// write code here

vector sign(9, false);

for(int i=m;i<=n;i++) {

for(int j=0;j<9;j++) {

sign[j] = true;

backtrack(j, sign, 1, i);

sign[j] = false;

}

}

return ans;

}

void backtrack(int cur, vector&sign, int cnt, int maxi) {

if(cnt==maxi)  {

ans++;

return;

}

for(int i=0;i<9;i++) {

if(i==cur)    continue;

if(d[cur][i]==0) {

if(!sign[i]) {

sign[ i ] = true;

backtrack(i, sign, cnt+1, maxi);

sign[ i ] = false;

}

}

else {

if(sign[ d[cur][i] ] && !sign[i]) {

sign[ i ] = true;

backtrack(i, sign, cnt+1, maxi);

sign[i] = false;

}

}

}

}

};

发表于 2020-08-15 19:04:07

回复(0)

0

#

# 实现方案

# @param m int整型 最少m个键

# @param n int整型 最多n个键

# @return int整型

#

class Solution:

def solution(self , m , n ):

# write code here

# deps[i][j] := i to j is ok when deps[i][j] exists

deps = {

1<<0:{1<<2:1<<1,1<<6:1<<3,1<<8:1<<4},

1<<1:{1<<7:1<<4},

1<<2:{1<<0:1<<1,1<<6:1<<4,1<<8:1<<5},

1<<3:{1<<5:1<<4},

1<<4:{},

1<<5:{1<<3:1<<4},

1<<6:{1<<0:1<<3,1<<2:1<<4,1<<8:1<<7},

1<<7:{1<<1:1<<4},

1<<8:{1<<0:1<<4,1<<2:1<<5,1<<6:1<<7},

}

def getlen(nums):

cnt = 0

while nums>0:

nums -= nums & -nums

cnt += 1

return cnt

def getbit(nums):

while nums > 0:

yield nums & -nums

nums -= nums & -nums

ans = [0] * 10

tables = {}

for state in range(1,1<<9):

tables[state] = {}

length = getlen(state)

if length == 1:

tables[state][state] = 1

ans[length] += 1

continue

for u in getbit(state):

tables[state][u] = 0

old_state = state - u

for v in getbit(old_state):

if u not in deps[v]&nbs***bsp;(old_state & deps[v][u]) > 0:

tables[state][u] += tables[old_state][v]

ans[length] += tables[state][u]

n = min(n,9)

total = 0

for i in range(m,n+1):

total += ans[i]

return total

发表于 2020-08-01 11:39:20

回复(0)

0

Python, 38 ms. 在init里面用状态压缩DP把每一个长度的和求出来，query的时候直接查就行了。记得在LC里面用这个方法runtime击败了96%的submission。

class Solution:

def __init__(self):

self.resTable = [0 for _ in range(10)]

premises = {(1<<0):{(1<<2):(1<<1),(1<<8):(1<<4),(1<<6):(1<<3)},

(1<<1):{(1<<7):(1<<4)},

(1<<2):{(1<<0):(1<<1),(1<<6):(1<<4),(1<<8):(1<<5)},

(1<<3):{(1<<5):(1<<4)},(1<<4):{},

(1<<5):{(1<<3):(1<<4)},

(1<<6):{(1<<0):(1<<3),(1<<2):(1<<4),(1<<8):(1<<7)},

(1<<7):{(1<<1):(1<<4)},

(1<<8):{(1<<2):(1<<5),(1<<0):(1<<4),(1<<6):(1<<7)}}

table = {}#mask:out:res

for m in xrange(1,1<<9):

table[m] = {}

m0,length = m,0

while m0>0:

length += 1

m0 -= m0&-m0

if m == (m&-m):

table[m][m] = 1

self.resTable[1] += 1

else:

m0 = m

while m0>0:

out0 = m0&-m0

table[m][out0] = 0

m1 = m-out0

m2 = m1

while m2>0:

out1 = m2&-m2

if out1 not in premises[out0] or (m1&premises[out0][out1]) > 0:

table[m][out0] += table[m1][out1]

m2 -= out1

m0 -= out0

self.resTable[length] += table[m][out0]

def solution(self , m , n ):

# write code here

n = min(n,9)

res = 0

for i in xrange(m,n+1):

res += self.resTable[i]

return res

编辑于 2020-06-30 17:32:05

回复(1)

0

典型的回溯问题。

主要问题是怎么选下一个点，一开始理解错了题目表达的意思。

其实题目表达的意思翻译一下就是，有两种非法访问：

1. 如果当前键到下一个键会经过中间键，那么这个中间键必须已经访问过了，若还没访问那就非法

2. 下一个键若已经访问过了是非法。

import java.util.*;

public class Solution {

public static int pathSum = 0;

static class Pos{

int x;

int y;

Pos(int x,int y){

this.x = x;

this.y = y;

}

}

public int solution(int m,int n){

//异常处理

if(m > n || m  9){

return 0;

}

if(n>9)

n=9;

//保存访问情况

int[][] map = new int[3][3];

while(m <= n){

//从9个点中选择一个起点

for(int i=0;i<3;i++)

for(int j=0;j<3;j++){

for(int k=0;k

Arrays.fill(map[k],0);

Pos start = new Pos(i,j);

map[start.x][start.y] = 1;

BackTrack(start,m,1,map);

}

m++;

}

return pathSum;

}

public void BackTrack(Pos start, int maxLen,int pathLen, int[][] map){

if(pathLen == maxLen){

pathSum++;

return;

}else {

//遍历9个点

for (int i = 0; i <= 2; i++) {

for (int j = 0; j <= 2; j++) {

Pos newStart = new Pos(i, j);

//检验新的键是否符合要求

if (canVisit(map, start, newStart)) {

map[newStart.x][newStart.y] = 1;

//回溯

BackTrack(newStart, maxLen,pathLen+1,map);

map[newStart.x][newStart.y] = 0;

}

}

}

}

}

public boolean canVisit(int[][] map,Pos curPos, Pos newPos){

//首先新键和当前键不能相同

if(!(curPos.x == newPos.x && curPos.y == newPos.y)){

//两个键之间存在中间键

if((curPos.x-newPos.x)%2 == 0 &&(curPos.y-newPos.y)%2 == 0){

Pos mid = new Pos((curPos.x+newPos.x)/2,(curPos.y+newPos.y)/2);

//中间键已经访问过了

if(map[mid.x][mid.y] == 1){

return map[newPos.x][newPos.y] == 0;

}else

return false;

}else {

//其他情况只要是之前没访问过的键都行

return map[newPos.x][newPos.y] == 0;

}

}

return false;

}

}

发表于 2020-06-19 23:18:47

回复(0)

0

DFS，深度遍历。

用一个栈存放键的位置int[]{i,j}，遍历到下一个没访问的键。判断这个键的位置与栈顶(peek)键位置关系。

(1)在同一横行，Math.abs(i-peek[0])>1，j==peek[1]；

(2)在同一竖行，Math.abs(j-peek[1])>1，i==peek[0]；

(3)在对角线上，Math.abs(j-peek[1])>1，Math.abs(i-peek[0])>1；

满足之一，就判断它们的中点是否被访问过：key[(i+temp[0])/2][(j+temp[1])/2]==0？

等于0，不满足有效模式，return；

不等于0，满足有效模式，继续递归；

不满足上面三个位置关系，肯定满足有效模式，继续递归； public class Solution {

int m,n;

int sum=0;

public int solution (int m, int n) {

if(n==0) return 0;

if(m==0) m=1;

this.m=m;

this.n=n;

int[][] key=new int[3][3];

Stack ls=new Stack<>();

dfs(key,ls);

return sum;

}

public void dfs(int[][] key,Stack ls){

if(ls.size()>=n){

sum++;

return;

}

if(ls.size()>=m && ls.size()

sum++;

}

for(int i=0;i<3;i++){

for(int j=0;j<3;j++){

if(key[i][j]!=0) continue;

if(ls.isEmpty()){

key[i][j]=1;

ls.push(new int[]{i,j});

dfs(key,ls);

key[i][j]=0;

ls.pop();

}else{

int[] temp=ls.peek();

if((Math.abs(i-temp[0])>1 && j==temp[1]) ||

(Math.abs(j-temp[1])>1 && i==temp[0]) ||

(Math.abs(j-temp[1])>1 && Math.abs(i-temp[0])>1)){

if(key[(i+temp[0])/2][(j+temp[1])/2]!=0){

key[i][j]=1;

ls.push(new int[]{i,j});

dfs(key,ls);

key[i][j]=0;

ls.pop();

}else{

continue;

}

}else{

key[i][j]=1;

ls.push(new int[]{i,j});

dfs(key,ls);

key[i][j]=0;

ls.pop();

}

}

}

}

}

}

发表于 2020-06-06 22:57:47

回复(0)