一个回溯算法

一只魈咸鱼

请问下面程序错在哪了呢，为什么bad函数里面明明pos[y]>max_y了它却不比较呢？
里面那个注释写错了，我程序输入的是：
0 0
0 1
终点坐标是1,1

源代码“：
#用户输入m行n列字符串，不存在处为-1，存在处为0（非终点）或1（终点）
#创建递归函数
route_dict = {}
move_lst = [(0,1),(0,-1),(1,0),(-1,0)]
def bad(pos):
    print(pos[1],max_y)
    if pos[0]<0 or pos[0]>max_x:
        return True
    if pos[1]<0 or pos[0]>max_y:
        print('hi')
        return True
    if f'{pos[0]},{pos[1]}' in route_dict:
        return True
def traceback_fn(start):
    global route_dict
    for move in move_lst:
        if bad(start):
            continue
        next_start = start[0]+move[0],start[1]+move[1]
        print(next_start)
        if rows[next_start[0]][next_start[0]] == '1':
            return True
        if traceback_fn(next_start):
            route_dict[f'{start[0]},{start[1]}']='6'
            return True
    return False

rows = []
pos_dict = {}
max_y = -1

while True:
    j = input()
    if j:
        row = j.split()
        rows.append(row)
        max_y+=1
    else:
        break
max_x = len(rows[0])-1
'''
#pos_dict记录各坐标的状态
for y in range(max_y):
    for x in range(max_x):
        pos_dict[f'{x},{y}'] = rows[y][x]
'''
traceback_fn((0,0))
print(route_dict)
还有一个小问题，dict.items返回的是什么类型呢？网上查是列表，但是用type显示的是dict_items

louxinghao

哎。。。
截图也行，发代码也行，你这样根本没人有心情仔细看你的代码

wwwccc

有点模糊啦，好兄弟搞个截图软件呀

小伤口

左上角有贴代码的，我们想修改一下还得抄一遍吗

一只魈咸鱼

加上了，抱歉

傻眼貓咪

兄弟，你直接給我題目，和想要的結果吧，我幫你重新寫過全部代碼吧。
至於你問說dict.items返回什麼？
就是字典裡面的東西，如果你想列表化，前面加個list()函數，如下：

1. x = {'banana': 13, 'apple': 5, 'stawberry': 7}
   
2. 
   
3. y = x.items()
   
4. z = list(x.items())
   
5. 
   
6. print('y:', y)
   
7. print('z:', z)

复制代码

輸出結果：

1. y: dict_items([('banana', 13), ('apple', 5), ('stawberry', 7)]) # <class 'dict_items'>
   
2. z: [('banana', 13), ('apple', 5), ('stawberry', 7)] # <class 'list'>

复制代码

一只魈咸鱼

傻眼貓咪 发表于 2021-9-3 19:35
兄弟，你直接給我題目，和想要的結果吧，我幫你重新寫過全部代碼吧。
至於你問說dict.items返回什麼？
就 ...

好的好的，麻烦你了！
问题如下：
一平面上是MxN个格子，其中一个格子是终点，比如4x4的格子：
0 0 0 0
0 0 0 0
0 0 1 0
0 0 0 0
此处1是终点，一蚂蚁可选择除终点格子的任意一个作为起点，当蚂蚁到达终点且所有格子都留下了蚂蚁的痕迹游戏结束，此过程蚂蚁不能出界，不能踩已经踩过的格子。
要求出一个胜利方案，即：起点与路线