無論我在這段簡短的代碼塊中進行什么更改，我都不會達到 38。```grid = [[0, 0,? 0, 0,? 0, 1],? ? ? ? [0, 0,? 0, 0,? 0, 0],? ? ? ? [0, 0,? 0, 0,? 0, 0],? ? ? ? [1, 0,? 0, 0,? 0, 0]]solution = 0def number_of_paths(x, y):? ? global solution? ? global grid? ? for i in range(0, x):? ? ? ? for j in range(0, y):? ? ? ? ? ? if grid[i][j] == 0:? ? ? ? ? ? ? ? grid[i][j] = 1? ? ? ? ? ? ? ? number_of_paths(x, y)? ? ? ? ? ? ? ? grid[i][j] = 0? ? ? ? ? ? ? ? solution += 1? ? returnif __name__ == '__main__':? ? number_of_paths(2, 3)? ? print(grid)? ? print(solution)```這是一個使用數(shù)獨求解器求解的示例解決方案。```grid = [[5, 3, 0, 0, 7, 0, 0, 0, 0],?? ? ? ?[6, 0, 0, 1, 9, 5, 0, 0, 0],? ? ? ?[0, 9, 8, 0, 0, 0, 0, 6, 0],? ? ? ?[8, 0, 0, 0, 6, 0, 0, 0, 3],? ? ? ?[4, 0, 0, 8, 0, 3, 0, 0, 1],? ? ? ?[7, 0, 0, 0, 2, 0, 0, 0, 6],? ? ? ?[0, 6, 0, 0, 0, 0, 2, 8, 0],? ? ? ?[0, 0, 0, 4, 1, 9, 0, 0, 5],?? ? ? ?[0, 0, 0, 0, 8, 0, 0, 7, 9]]import numpy as npdef possible(y, x, n):? ? global grid? ? for i in range(0, 9):? ? ? ? if grid[y][i] == n:? ? ? ? ? ? return False? ? for i in range(0, 9):? ? ? ? if grid[i][x] == n:? ? ? ? ? ? return False? ? x0 = (x // 3) * 3? ? y0 = (y // 3) * 3? ? for i in range(0, 3):? ? ? ? for j in range(0, 3):? ? ? ? ? ? if grid[y0 + i][x0 + j] == n:? ? ? ? ? ? ? ? return False? ? return Truedef solve():? ? global grid? ? for y in range(9):? ? ? ? for x in range(9):? ? ? ? ? ? if grid[y][x] == 0:? ? ? ? ? ? ? ? for n in range(1, 10):? ? ? ? ? ? ? ? ? ? if possible(y, x, n):? ? ? ? ? ? ? ? ? ? ? ? grid[y][x] = n? ? ? ? ? ? ? ? ? ? ? ? solve()? ? ? ? ? ? ? ? ? ? ? ? # backtracking - bad choice? ? ? ? ? ? ? ? ? ? ? ? grid[y][x] = 0? ? ? ? ? ? ? ? return? ? print(np,matrix(grid))? ? input("More?")```
2 回答
大話西游666
TA貢獻1817條經(jīng)驗 獲得超14個贊
一些建議：
您可能希望將集合用于網(wǎng)格，如果它還不是集合的成員，則在訪問它時立即添加一個正方形。
計數(shù)器和網(wǎng)格可以是全局的，但一開始將它們作為函數(shù)的參數(shù)可能會更容易。當(dāng)解決方案更加清晰之后，您就可以擔(dān)心這些細節(jié)了。
你解決問題的方式是錯誤的。最好有一個函數(shù)計算從起點到目的地的路徑數(shù)（通過調(diào)用尚未訪問過的鄰居的函數(shù)。確保更新網(wǎng)格）。最重要的是，您可以有一個函數(shù)為起點和終點的每個組合調(diào)用路徑函數(shù)。一個小提示：您不必反向計算相同的路徑！您可以獲得計算路徑總和的地圖。如果相反的方向已經(jīng)計算出來了，就不用麻煩了。隨后，將路徑數(shù)量加倍 2。
祝你好運！
繁華開滿天機
TA貢獻1816條經(jīng)驗 獲得超4個贊
我將向您展示坐標(biāo)系上的解決方案，其中 (0,0) 是左上角，(maxY,maxX) 是機器人右側(cè)。向右移動會增加 x，向下移動會增加 y。
1-如果您試圖解決圖像中的精確迷宮問題，那么您的網(wǎng)格陣列形狀是錯誤的。請注意，您在正方形的角之間移動，有 4 個點可以水平移動，3 個點可以垂直移動。
2-提示告訴您有關(guān)對訪問狀態(tài)使用布爾掩碼，您已經(jīng)有一個網(wǎng)格數(shù)組，因此不需要單獨的數(shù)組。
3-您的代碼的主要問題是您在迷宮中的進展情況。循環(huán)結(jié)構(gòu)
for i in range(0, x): for j in range(0, y):
沒有意義，因為當(dāng)你處于 (x, y) 位置時，你只能向 4 個主要方向移動（右、上、左、下）。然而，這個循環(huán)讓你看起來像是在嘗試分支到你身后的所有位置，這是無效的。在我的代碼中，我將明確展示這個遍歷的東西。
grid = [[0, 0, 0, 0],
[0, 0, 0, 0],
[1, 0, 0, 0]]
# number of solutions
solution = 0
# maximum values of x and y coordinates
maxX = len(grid[0])-1
maxY = len(grid)-1
# endpoint coordinates, top(y=0) right(x=maxX) of the maze
endX = maxX
endY = 0
# starting point coordinates, bottom(y=maxY) left(x=0) of the maze
mazeStartX = 0
mazeStartY = maxY
def number_of_paths(startX, startY):
global solution
global grid
global mask
# if we reached the goal, return at this point
if (startX == endX and startY == endY):
solution += 1
return
# possible directions are
#RIGHT (+1x, 0y)
#UP (0x, -1y)
#LEFT (-1x, 0y)
#DOWN (0x, +1y)
# I use a direction array like this to avoid nested ifs inside the for loop
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
for d in range(len(dx)):
newX = startX + dx[d]
newY = startY + dy[d]
# out of maze bounds
if (newX < 0 or newY < 0):
continue
# out of maze bounds
if (newX > maxX or newY > maxY):
continue
if (grid[newY][newX] == 1):
# this are is already visited
continue
else:
# branch from this point
grid[newY][newX] = 1
number_of_paths(newX, newY)
grid[newY][newX] = 0
if __name__ == '__main__':
number_of_paths(mazeStartX, mazeStartY)
print(grid)
print(solution)
添加回答
舉報
0/150
提交
取消