[已解决]一个类似数独的迷宫问题（新开一贴）

昭昭天命amg

                               
登录/注册后可看大图

感觉用回溯算法应该能实现，我有点思路，但是代码实现不了，求大神指点
之前图片太糊，于是新开一贴

最佳答案

月排行榜 / 总排行榜

myd0311

2023-4-1 16:38:13

现在好了，nx ny 搞反了：

1. 
   
2. d = [[1, 0], [-1, 0], [0, -1], [0, 1]]
   
3. l_rem = [-1, 1, 1, 3, 3, 4, 5, 6] # 列剩余
   
4. r_rem = [-1, 5, 3, 5, 1, 3, 2, 4] # 行剩余
   
5. vis = [[0 for i in range(8)] for i in range(8)]
   
6. vis[1][1] = 1
   
7. l_rem[1] -= 1
   
8. r_rem[1] -= 1
   
9. def solve(x, y):
   
10.     if x == 7 and y == 7:
    
11.         ok = 1
    
12.         for i in range(1, 8):
    
13.             if l_rem[i] != 0 or r_rem[i] != 0:
    
14.                 ok = 0
    
15.                 break
    
16.         if ok == 1:
    
17.             for i in range(1, 8):
    
18.                 for j in range(1, 8):
    
19.                     print(vis[i][j], end = " ")
    
20.                 print()
    
21.             exit(0)
    
22.     for i in d:
    
23.         nx = x + i[0]
    
24.         ny = y + i[1]
    
25.         if nx >= 1 and nx <= 7 and ny >= 1 and ny <= 7 and vis[nx][ny] == 0:
    
26.             if l_rem[ny] >= 0 and r_rem[nx] >= 0:
    
27.                 l_rem[ny] -= 1
    
28.                 r_rem[nx] -= 1
    
29.                 vis[nx][ny] = 1
    
30.                 solve(nx, ny)
    
31.                 l_rem[ny] += 1
    
32.                 r_rem[nx] += 1
    
33.                 vis[nx][ny] = 0
    
34. solve(1, 1)
    

复制代码

最后输出：

1. 1 1 1 0 0 1 1
   
2. 0 0 1 0 0 1 1
   
3. 0 0 1 1 1 1 1
   
4. 0 0 0 0 0 0 1
   
5. 0 0 0 0 1 1 1
   
6. 0 0 0 1 1 0 0
   
7. 0 0 0 1 1 1 1

复制代码

这样一来，具体怎么走也就很简单了

跳转到最佳答案楼层

myd0311

请问一共多少行，多少列，数据范围总得给出来呀

昭昭天命amg

myd0311 发表于 2023-4-1 16:16
请问一共多少行，多少列，数据范围总得给出来呀

就是图里下面那个啊，上面那个是例子，是我图又没传全吗

myd0311

虽然这个回溯法是可行的，但是回溯法的时间复杂度是指数级别的，行列一旦多了就会超时，我有一个 广度优先搜索 的想法，每一个状态都记录每一行的剩余值，每一列的剩余值，以及当前坐标，那么对于示例就一共有 7 ** 7 * 49 = 40353607 以下的状态，应该是能过去的，但是一旦列行超过了 10 就不好整了，可能会涉及到 dp

myd0311

昭昭天命amg 发表于 2023-4-1 16:20
就是图里下面那个啊，上面那个是例子，是我图又没传全吗

我懂了，这个回溯有可能会超时，为了节约时间，要不写个 广度优先搜索吧

C++ 可以么？

昭昭天命amg

myd0311 发表于 2023-4-1 16:24
我懂了，这个回溯有可能会超时，为了节约时间，要不写个 广度优先搜索吧

C++ 可以么？

我没学过C++，只会java和python...

myd0311

等等，我搞反了，上面的不对

myd0311

现在好了，nx ny 搞反了：

1. 
   
2. d = [[1, 0], [-1, 0], [0, -1], [0, 1]]
   
3. l_rem = [-1, 1, 1, 3, 3, 4, 5, 6] # 列剩余
   
4. r_rem = [-1, 5, 3, 5, 1, 3, 2, 4] # 行剩余
   
5. vis = [[0 for i in range(8)] for i in range(8)]
   
6. vis[1][1] = 1
   
7. l_rem[1] -= 1
   
8. r_rem[1] -= 1
   
9. def solve(x, y):
   
10.     if x == 7 and y == 7:
    
11.         ok = 1
    
12.         for i in range(1, 8):
    
13.             if l_rem[i] != 0 or r_rem[i] != 0:
    
14.                 ok = 0
    
15.                 break
    
16.         if ok == 1:
    
17.             for i in range(1, 8):
    
18.                 for j in range(1, 8):
    
19.                     print(vis[i][j], end = " ")
    
20.                 print()
    
21.             exit(0)
    
22.     for i in d:
    
23.         nx = x + i[0]
    
24.         ny = y + i[1]
    
25.         if nx >= 1 and nx <= 7 and ny >= 1 and ny <= 7 and vis[nx][ny] == 0:
    
26.             if l_rem[ny] >= 0 and r_rem[nx] >= 0:
    
27.                 l_rem[ny] -= 1
    
28.                 r_rem[nx] -= 1
    
29.                 vis[nx][ny] = 1
    
30.                 solve(nx, ny)
    
31.                 l_rem[ny] += 1
    
32.                 r_rem[nx] += 1
    
33.                 vis[nx][ny] = 0
    
34. solve(1, 1)
    

复制代码

最后输出：

1. 1 1 1 0 0 1 1
   
2. 0 0 1 0 0 1 1
   
3. 0 0 1 1 1 1 1
   
4. 0 0 0 0 0 0 1
   
5. 0 0 0 0 1 1 1
   
6. 0 0 0 1 1 0 0
   
7. 0 0 0 1 1 1 1

复制代码

这样一来，具体怎么走也就很简单了

昭昭天命amg

myd0311 发表于 2023-4-1 16:38
现在好了，nx ny 搞反了：

最后输出：

大佬啊！感谢！不过这种写法也是回溯吧

myd0311

昭昭天命amg 发表于 2023-4-1 16:57
大佬啊！感谢！不过这种写法也是回溯吧

对呀，这是回溯，因为不能重复走嘛

如果有用，求给一个最佳答案，感谢

bfs 也可以，只是十分麻烦