移动方格

题目描述

有一个N*M的矩阵，且矩阵中每个方格中都有一个整数（0≤整数≤100），小蓝需要按照以下要求从矩阵中找出一条最长的移动路线，且输出最长路线的长度（1个方格为1个长度）。

要求： 1.小蓝可以从矩阵中任意一个方格开始向它的上、下、左、右相邻的任意一个方格移动，且移动的路线不能有交叉； 2.小蓝每次所要移动到的方格中的整数都要小于当前所在方格中的整数（如当前所在的方格中的整数为3，那么可以移动到数字为0，1，2的格子里，不可以移动到数字为3，4，5...的格子里）；

例如：N=3，M=3，矩阵方格如下：最长路线为4 -> 3 -> 2 -> 1，故路线长度为4。

输入描述

第一行输入两个正整数N，M（1＜N≤1000，1＜M≤1000），N表示矩阵的行数，M表示矩阵的列数，两个正整数之间以一个空格隔开

第二行开始输入N行，每行包含M个整数（0≤每个整数≤100），表示每个方格中的整数，每个整数之间以一个空格隔开

输出描述

输出一个整数，表示最长路线的长度

样例输入

3 3

1 1 3

2 3 4

1 1 1

样例输出

4

代码详解

展开查看

matrix = input().split(" ")
N = matrix[0]
M = matrix[1]
res = []
times = []
for i in range(int(N)):
    ans = input().split(" ")
    res.append(ans)

def dfs(res, N, M, i, j, num, k, flag):
    # print("开始尝试，坐标为",i,j,"移动次数",k)
    if k != 0:
        if i<0 or i>=int(N) or j<0 or j>=int(M) or res[i][j]>=num or flag[i][j]:
            # print("尝试失败，继续移动")
            return False
    flag[i][j] = True
    num = res[i][j]
    if (dfs(res, N, M, i-1, j, num, k+1, flag)
        or dfs(res, N, M, i+1, j, num, k+1, flag)
        or dfs(res, N, M, i, j-1, num, k+1, flag)
        or dfs(res, N, M, i, j+1, num, k+1, flag)):
        return True
    flag[i][j] = False
    times.append(k)
    return Falsedef hasPath():
    flag = []
    for i in range(3):
        flag.append([])
        for j in range(3):
            flag[i].append(False)

    for i in range(int(N)):
        for j in range(int(M)):
            num = res[i][j]
            if dfs(res, N, M, i, j, num, 0, flag):
                return True
    times.sort()
    print(times[-1] + 1)
    return False

if __name__ == '__main__':
    hasPath()

运行结果

展开查看