失眠网 > python破解手机锁屏密码_手机屏幕解锁模式

python破解手机锁屏密码_手机屏幕解锁模式

时间：2023-01-17 23:10:26

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

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

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

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

2.其余的八个方向

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

以下为DFS代码

intdir[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}

};

intisVisit[5][5];//是否已按下

boolcanVisit(inti,intj){//判断能否按下

if(i3||j3||isVisit[i][j])returnfalse;

returntrue;

}

inttimes[10];

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

voidDFS(inti,intj,intd){

if(d==9){

return;

}

isVisit[i][j]=true;

times[d++]++;

//选择下一个键

for(inty=0;y

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

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

DFS(ni,nj,d);

}

elseif(y

ni+=dir[y][0];

nj+=dir[y][1];

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

DFS(ni,nj,d);

}

isVisit[i][j]=false;

return;

} solution：

classSolution{

public:

intsolution(intm,intn){

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

return0;

}

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

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

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

intans=0;

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

ans+=tmp[i];

}

returnans;

}

};

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

classSolution{

public:

voidmove(vector>&board,inti,intj,intk,intm,intn,int&ans){

//如果已经走过的点数大于等于m，则是有效路径，ans++

if(k>=m)ans++;

//如果已经走过的点数等于n，则不需要继续探索，故返回

if(k==n)return;

//如果已经走过的点数小于n，则还可以继续探索

for(intdx=-2;dx<=2;dx++){

for(intdy=-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;

}

intsolution(intm,intn){

//writecodehere

vector>board(3,vector(3,0));

intans=0;

//如果n等于0，则直接返回0

if(n==0)returnans;

//选择棋盘上任意一点作为起点

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

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

board[i][j]=1;

move(board,i,j,1,m,n,ans);

board[i][j]=0;

}

returnans;

}

};

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

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

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

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;

}

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

importjava.util.*;

图形密码即使图案相同，但是顺序不同的话也算作一种

dfs，以每个位置作为起点，然后走[n,m]个点

当走到无路可走的时候，如果走的点小于m，那么该路径不满足要求

当已经走的点>n的时候，那么表示接下来的路径也不满足要求，直接返回

当我们发现周围几个点都已经走过了，如果是普通的dfs，这时候已经返回了

但是，我们可以越过已经访问过的点，继续往下一个点走，因此我们需要判断

8个方向第2个点是否已经访问过了，如果没有，那么可以继续访问

注意：只有我们发现某个方向上的点访问过了才可以越过该点

如果该方向上的第一个点还没有访问，那么我们不能直接越过

publicclassSolution{

/**

*实现方案

*@parammint整型最少m个键

*@paramnint整型最多n个键

*@returnint整型

publicintsolution(intm,intn){

//范围处理

if(m>n){

return0;

}

m=Math.max(0,m);

n=Math.min(9,n);

if(n==0){

return0;

}

//writecodehere

res=0;

visited=newboolean[3][3];

for(inti=0;i

for(intj=0;j

dfs(i,j,m,n,1);

}

returnres;

}

staticintres;

staticboolean[][]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}

};

privatevoiddfs(inti,intj,intm,intn,intp){

if(p>=m){

res++;

}

//当访问个数大于等于n个，那么已经足够了，无需继续访问

if(p>=n){

return;

}

visited[i][j]=true;

//8个方向走一遍

for(int[]po:pos){

intx=i+po[0];

inty=j+po[1];

if(!isEvil(x,y)){

if(!visited[x][y]){

dfs(x,y,m,n,p+1);

}else{

//越过同方向上的点

intxx=x+po[0];

intyy=y+po[1];

if(!isEvil(xx,yy)&&!visited[xx][yy]){

//越过(x,y)点，访问下一个点

dfs(xx,yy,m,n,p+1);

}

visited[i][j]=false;

}

privatebooleanisEvil(inti,intj){

returni=3||j=3;

}

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

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

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

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

}

发表于 -05-31 21:11:35

//提交时间：-04-29语言：C++运行时间：50ms占用内存：504K状态：答案正确

classSolution{

public:

boolcheck(inti,intj){

if((i>=0&&i<=2)&&(j>=0&&j<=2)&&!isVisit(i,j)){

returntrue;

}

returnfalse;

}

boolisVisit(inti,intj){returnvisited[i][j]==0?false:true;}

intvisited[5][5]={0};

intmap[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}};

intdfs(inti,intj,intdepth){

if(depth==1){

return1;

}elseif(depth==0){

return0;

}

intnum=0;

visited[i][j]=1;

for(intk=0;k

intpi=i+map[k][0];

intpj=j+map[k][1];

if(check(pi,pj)){

num+=dfs(pi,pj,depth-1);

}elseif(k

pi+=map[k][0];

pj+=map[k][1];

if(check(pi,pj)){

num+=dfs(pi,pj,depth-1);

}

visited[i][j]=0;

returnnum;

}

/**

*实现方案

*@parammint整型最少m个键

*@paramnint整型最多n个键

*@returnint整型

intsolution(intm,intn){

intcount=0;

m=m>=0&&m<=9?m:0;

n=n>=0&&n<=9?n:9;

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

for(inti=0;i

for(intj=0;j

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

}

returncount;

}

};

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

importjava.util.*;

publicclassSolution{

/**

*实现方案

*@parammint整型最少m个键

*@paramnint整型最多n个键

*@returnint整型

privateint[][]direction=newint[][]{

{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}}; //方向数组

privateint[]arr; //结果数组，每个arr[i]存的是i个操作形成的模式数量

privateintn; //输入的n，全局化，不用传参

publicintsolution(intm,intn){

//writecodehere

arr=newint[n+1];

this.n=n;

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

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

booleanhasVisited[][]=newboolean[3][3]; //是否访问过当前元素

hasVisited[i][j]=true;

dfs(i,j,1,hasVisited);

}

intret=0;

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

ret+=arr[i];

}

returnret;

}

privatevoiddfs(inti,intj,intcount,boolean[][]visited){

if(count>n){

return;

}

arr[count]++;

for(int[]d:direction){

intx=i+d[0];

inty=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{

intnX=x+d[0]; //夸过已访问的中间的值访问隔壁的值，隔山打牛

intnY=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;

}

发表于 -12-31 10:46:16

classSolution{

public:

/**

*实现方案

*@parammint整型最少m个键

*@paramnint整型最多n个键

*@returnint整型

intsolution(intm,intn){

vectorvis(9);

return4*(dfs(0,1,vis,m,n)+dfs(1,1,vis,m,n))+dfs(4,1,vis,m,n);

}

intdfs(inti,intcnt,vectorvis,intm,intn){

if(cnt>n)return0;

intres=cnt>=m?1:0;

vis[i]=true;

intx=i/3,y=i%3;

for(intj=0;j

if(vis[j])continue;

intxx=j/3,yy=j%3;

intdx=abs(x-xx),dy=abs(y-yy);

inta=min(dx,dy),b=max(dx,dy);

if(b<=1||a==1&&b==2){

res+=dfs(j,cnt+1,vis,m,n);

}

else{

intxmid=(x+xx)/2,ymid=(y+yy)/2;

if(vis[xmid*3+ymid])res+=dfs(j,cnt+1,vis,m,n);

}

returnres;

}

};

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

#打个表通过

classSolution:

defsolution(self,m,n):

#writecodehere

candi=[0,9,56,320,1624,7152,26016,72912,140704,140704]

res=0

foriinrange(m,n+1):

ifi==0:continue

ifi>9:break

res+=candi[i]

returnres

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

classSolution:

defsolution(self,m,n):

#writecodehere

res=0

foriinrange(m,n+1):

ifi==0:continue

res+=pute(i)

returnres

defcompute(self,k):

t=0

board=[['.']*3for_inrange(3)]

self.x=-1

self.y=-1

defisValid(board,row,col):

ifself.x==-1andself.y==-1:

returnTrue

ifabs(row-self.x)>1andcol==self.y:

ifboard[(row+self.x)//2][col]!='Q':

returnFalse

elifabs(col-self.y)>1androw==self.x:

ifboard[row][(col+self.y)//2]!='Q':

returnFalse

elifabs(col-self.y)>1andabs(row-self.x)>1:

ifboard[(row+self.x)//2][(col+self.y)//2]!='Q':

returnFalse

returnTrue

deftrackback(board,k,path):

ifk==0:

t+=1

self.x,self.y=path[-2]

return

foriinrange(3):

forjinrange(3):

ifboard[i][j]=='Q':continue

ifnotisValid(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)])

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

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

#实现方案:DFS

#编码方案：[123

#456

#789]

classSolution:

defsolution(self,m,n):

ifm>n or n<=0:

return0

#边界修正(还能有[3,20]这种测试也是醉了)

ifm<=0:

m=1

ifn>9:

n=9

#初始数据：保存1-9长度路径和，原始结点的set，当前所有路径

ret=[9]

oriSet=set(range(1,10))

currList=[[1],[2],[3],[4],[5],[6],[7],[8],[9]]

for_inrange(2,n+1):

nextList=[]

forcurrlineincurrList:

foriin(oriSet-set(currline)):

ifself.isValid(currline,i):

tmp=currline[:]+[i]

nextList.append(tmp)

currList=nextList

ret.append(len(currList))

returnsum(ret[m-1:n])

defisValid(self,currline,i):

#判断currline能否增加i这个结点

#此时为空，或者中点不是整数

ifcurrline==[] or (currline[-1]+i)%2==1:

returnTrue

#此时mid必然是整数

mid=(currline[-1]+i)//2

midList=[{1,3},{4,6},{7,9},{1,7},{2,8},{3,9},{1,9},{3,7}]

ifmidincurrline&nbs***bsp;set([currline[-1],i])notinmidList:

returnTrue

else:

returnFalse

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

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

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

importjava.util.*;

publicclassSolution{

/**

*实现方案

*@parammint整型最少m个键

*@paramnint整型最多n个键

*@returnint整型

privateintsum=0;

publicintsolution(intm,intn){

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

returnsum;

}

privatevoidhelper(boolean[]hash,intnum,intm,intn,intcurr){

if(num==n)return;

for(inti=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;

}

privatebooleanisCorr(boolean[]hash,inti,intj){

if(i==-1)returnfalse;

if(i>j)returnisCorr(hash,j,i);

if(i==0){

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

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

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

}

if(i==2){

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

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

}

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

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

returnfalse;

}

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

有人跟我一样想用Java的吗

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

publicintsolution(intm,intn){

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

//递归实现

intcount=0;

if(n

return0;

}

if(m==0){

m=1;

}

n=n>9?9:n;

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

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

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

Listlist=newArrayList<>();

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

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

}

returncount;

}

publicintfindNext(Listlist,int[][]arr,intj,intk,intstep,intstepCount){

if(step>=stepCount){

//System.out.println(list);

return1;

}

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

intcount=0;

//上一步

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

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

ints=step;

intlastStep=arr[j][k];

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

booleanflag=true;

for(intr=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++;

Listintegers=newArrayList<>(list);

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

//System.out.println(integers);

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

}

returncount;

}

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

将九宫格的九个格子当做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 ] 是否已经被选择。

classSolution{

public:

/**

*实现方案

*@parammint整型最少m个键

*@paramnint整型最多n个键

*@returnint整型

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}

};

intans=0;

intsolution(intm,intn){

//writecodehere

vectorsign(9,false);

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

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

sign[j]=true;

backtrack(j,sign,1,i);

sign[j]=false;

}

returnans;

}

voidbacktrack(intcur,vector&sign,intcnt,intmaxi){

if(cnt==maxi){

ans++;

return;

}

for(inti=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;

}

};

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

#实现方案

#@parammint整型最少m个键

#@paramnint整型最多n个键

#@returnint整型

classSolution:

defsolution(self,m,n):

#writecodehere

#deps[i][j]:=itojisokwhendeps[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},

}

defgetlen(nums):

cnt=0

whilenums>0:

nums-=nums&-nums

cnt+=1

returncnt

defgetbit(nums):

whilenums>0:

yieldnums&-nums

nums-=nums&-nums

ans=[0]*10

tables={}

forstateinrange(1,1<<9):

tables[state]={}

length=getlen(state)

iflength==1:

tables[state][state]=1

ans[length]+=1

continue

foruingetbit(state):

tables[state][u]=0

old_state=state-u

forvingetbit(old_state):

ifunotindeps[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

foriinrange(m,n+1):

total+=ans[i]

returntotal

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

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

classSolution:

def__init__(self):

self.resTable=[0for_inrange(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

forminxrange(1,1<<9):

table[m]={}

m0,length=m,0

whilem0>0:

length+=1

m0-=m0&-m0

ifm==(m&-m):

table[m][m]=1

self.resTable[1]+=1

else:

m0=m

whilem0>0:

out0=m0&-m0

table[m][out0]=0

m1=m-out0

m2=m1

whilem2>0:

out1=m2&-m2

ifout1notinpremises[out0] or (m1&premises[out0][out1])>0:

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

m2-=out1

m0-=out0

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

defsolution(self,m,n):

#writecodehere

n=min(n,9)

res=0

foriinxrange(m,n+1):

res+=self.resTable[i]

returnres

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

典型的回溯问题。

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

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

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

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

importjava.util.*;

publicclassSolution{

publicstaticintpathSum=0;

staticclassPos{

intx;

inty;

Pos(intx,inty){

this.x=x;

this.y=y;

}

publicintsolution(intm,intn){

//异常处理

if(m>n||m9){

return0;

}

if(n>9)

n=9;

//保存访问情况

int[][]map=newint[3][3];

while(m<=n){

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

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

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

for(intk=0;k

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

Posstart=newPos(i,j);

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

BackTrack(start,m,1,map);

}

m++;

}

returnpathSum;

}

publicvoidBackTrack(Posstart,intmaxLen,intpathLen,int[][]map){

if(pathLen==maxLen){

pathSum++;

return;

}else{

//遍历9个点

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

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

PosnewStart=newPos(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;

}

publicbooleancanVisit(int[][]map,PoscurPos,PosnewPos){

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

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

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

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

Posmid=newPos((curPos.x+newPos.x)/2,(curPos.y+newPos.y)/2);

//中间键已经访问过了

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

returnmap[newPos.x][newPos.y]==0;

}else

returnfalse;

}else{

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

returnmap[newPos.x][newPos.y]==0;

}

returnfalse;

}

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

如果觉得《python破解手机锁屏密码_手机屏幕解锁模式》对你有帮助，请点赞、收藏，并留下你的观点哦！

本内容不代表本网观点和政治立场，如有侵犯你的权益请联系我们处理。

网友评论

网友评论仅供其表达个人看法，并不表明网站立场。