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