36
可以通过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
回复(5)
8
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
回复(2)
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)
编辑于 -04-02 18:52:08
回复(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;
}
发表于 -04-24 12:58:52
回复(5)
2
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
回复(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
发表于 -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+" ");
}
}
}
发表于 -05-31 21:11:35
回复(0)
2
//提交时间:-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
回复(0)
1
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
回复(0)
1
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
回复(0)
1
#打个表通过
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)])
t
供你们参考,和leetcode上面的N皇后思路差不多,DFS+剪枝
发表于 -06-07 00:22:18
回复(0)
1
#实现方案: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
回复(0)
1
本来以为有什么规律,结果浪费了很多时间,没想到还是暴力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
回复(0)
2
有人跟我一样想用Java的吗
发表于 -04-03 20:45:40
回复(1)
0
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
回复(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 ] 是否已经被选择。
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
回复(0)
0
#
#实现方案
#@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
回复(0)
0
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)
0
典型的回溯问题。
主要问题是怎么选下一个点,一开始理解错了题目表达的意思。
其实题目表达的意思翻译一下就是,有两种非法访问:
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
回复(0)