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)
8
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)
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)
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
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;
}
}
}
}
}
}
发表于 2020-12-31 10:46:16
回复(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)
