一个类似数独的迷宫问题（新开一贴）
https://t3.wodetu.cn/2023/04/01/6d4db72317c982bd333e315e341933b3.jpg感觉用回溯算法应该能实现，我有点思路，但是代码实现不了，求大神指点
之前图片太糊，于是新开一贴{:10_266:} 请问一共多少行，多少列，数据范围总得给出来呀 myd0311 发表于 2023-4-1 16:16
请问一共多少行，多少列，数据范围总得给出来呀
就是图里下面那个啊，上面那个是例子，是我图又没传全吗{:10_266:} 虽然这个回溯法是可行的，但是回溯法的时间复杂度是指数级别的，行列一旦多了就会超时，我有一个 广度优先搜索 的想法，每一个状态都记录每一行的剩余值，每一列的剩余值，以及当前坐标，那么对于示例就一共有 7 ** 7 * 49 = 40353607 以下的状态，应该是能过去的，但是一旦列行超过了 10 就不好整了，可能会涉及到 dp 昭昭天命amg 发表于 2023-4-1 16:20
就是图里下面那个啊，上面那个是例子，是我图又没传全吗
我懂了，这个回溯有可能会超时，为了节约时间，要不写个 广度优先搜索吧
C++ 可以么？ myd0311 发表于 2023-4-1 16:24
我懂了，这个回溯有可能会超时，为了节约时间，要不写个 广度优先搜索吧
C++ 可以么？
我没学过C++，只会java和python... 等等，我搞反了，上面的不对{:10_306:} 现在好了，nx ny 搞反了：
d = [, [-1, 0], , ]
l_rem = [-1, 1, 1, 3, 3, 4, 5, 6] # 列剩余
r_rem = [-1, 5, 3, 5, 1, 3, 2, 4] # 行剩余
vis = [ for i in range(8)]
vis = 1
l_rem -= 1
r_rem -= 1
def solve(x, y):
if x == 7 and y == 7:
ok = 1
for i in range(1, 8):
if l_rem != 0 or r_rem != 0:
ok = 0
break
if ok == 1:
for i in range(1, 8):
for j in range(1, 8):
print(vis, end = " ")
print()
exit(0)
for i in d:
nx = x + i
ny = y + i
if nx >= 1 and nx <= 7 and ny >= 1 and ny <= 7 and vis == 0:
if l_rem >= 0 and r_rem >= 0:
l_rem -= 1
r_rem -= 1
vis = 1
solve(nx, ny)
l_rem += 1
r_rem += 1
vis = 0
solve(1, 1)
最后输出：
1 1 1 0 0 1 1
0 0 1 0 0 1 1
0 0 1 1 1 1 1
0 0 0 0 0 0 1
0 0 0 0 1 1 1
0 0 0 1 1 0 0
0 0 0 1 1 1 1
这样一来，具体怎么走也就很简单了 myd0311 发表于 2023-4-1 16:38
现在好了，nx ny 搞反了：
最后输出：
大佬啊！感谢！不过这种写法也是回溯吧 昭昭天命amg 发表于 2023-4-1 16:57
大佬啊！感谢！不过这种写法也是回溯吧
对呀，这是回溯，因为不能重复走嘛
如果有用，求给一个最佳答案，感谢{:10_254:}
bfs 也可以，只是十分麻烦
页:
[1]