2024.10.19小米笔试题解

第一题数独计数

考虑dfs遍历所有情况

n = int(input())def check(grid, x, y, v):dx = [1, 0, -1, 0]dy = [0, 1, 0, -1]for i in range(4):nx, ny = x + dx[i], y + dy[i]if 0 <= nx < 3 and 0 <= ny < 3:if grid[nx][ny] == 0:continueif abs(grid[nx][ny] - v) == 1:return Falsereturn Truedef dfs(grid, vst, i):if i > 9:return 1if i in vst:return dfs(grid, vst, i+1)count = 0for x in range(3):for y in range(3):if (grid[x][y]==0 and check(grid, x, y, i)):grid[x][y] = icount += dfs(grid, vs