牛客网中《剑指 offer》矩阵中的路径一题 TestCase 不全。

[darkTianTian]

原题在这里：矩阵中的路径

我个人一般喜欢在 LeetCode 上刷题，不过有时候《剑指 Offer 》的题那里没有，会去牛客网上做。 之前就发现这道题在牛客网上测试用例不全，以为会修复，没想到几个月过去了，还是这样。把问题发到讨论区也没人理，也找不到合适的反馈入口。

这道题是用 Python 写的，排行榜上 Python 的大部分答案，我都认为是错的。

在一个特殊的 TestCase 下： matrix = 'ABEESFCSADME', rows=3, cols=4, path='SEE' 排行榜中大部分的答案都输出了错误的结果False,正确应该是True。

ABEE SFCS ADME

错误的答案都是这么写的，在 if 条件后直接 return 了，那么在四个方向判断中，如果先向下走，会导致提前 return False，而不会再向上延伸。

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        for i in range(rows):
            for j in range(cols):
                if matrix[i*cols+j] == path[0]:
                    if self.find(list(matrix),rows,cols,path[1:],i,j):
                        return True
        return False
    def find(self,matrix,rows,cols,path,i,j):
        if not path:
            return True
        matrix[i*cols+j]='0'
        if j+1<cols and matrix[i*cols+j+1]==path[0]:
            return self.find(matrix,rows,cols,path[1:],i,j+1)
        elif j-1>=0 and matrix[i*cols+j-1]==path[0]:
            return self.find(matrix,rows,cols,path[1:],i,j-1)
        elif i+1<rows and matrix[(i+1)*cols+j]==path[0]:
            return self.find(matrix,rows,cols,path[1:],i+1,j)
        elif i-1>=0 and matrix[(i-1)*cols+j]==path[0]:
            return self.find(matrix,rows,cols,path[1:],i-1,j)
        else:
            return False

我觉得正确的解法应该是这样，应该保留四个方向的结果做或运算。

def hasPath(matrix, rows, cols, path):
    # write code here
    for i in range(rows):
        for j in range(cols):
            if matrix[i*cols + j] == path[0]:
                if spread(list(matrix), rows, cols, path[1:], i, j):
                    return True
    return False

def spread(matrix, rows, cols, path, i, j):
    if not path:
        return True
    matrix[i*cols + j] = '-'
    up, down, left, right = False, False, False, False
    if j + 1 < cols and matrix[i * cols + j + 1] == path[0]:
        down = spread(matrix, rows, cols, path[1:], i, j + 1)
    if j - 1 >= 0 and matrix[i * cols + j - 1] == path[0]:
        left = spread(matrix, rows, cols, path[1:], i, j - 1)
    if i + 1 < rows and matrix[(i + 1) * cols + j] == path[0]:
        right = spread(matrix, rows, cols, path[1:], i + 1, j)
    if i - 1 >= 0 and matrix[(i - 1) * cols + j] == path[0]:
        up = spread(matrix, rows, cols, path[1:], i - 1, j)
    return up or down or left or right

上面两个代码均能通过牛客网的全部测试用例。而输出结果却不一致，我还是确信自己的写法是正确的。 有刷过此题的 V 友，或者算法大佬帮忙解答一下吗？就是想证明一下自己没有想错。

[doujiang]

```
def spread(matrix, rows, cols, path, i, j):
if not path:
return True
tmp = matrix[i*cols + j]
matrix[i*cols + j] = '-'
****
matrix[i*cols + j] = tmp
return up or down or left or right
```
测试样例确实弱，应该回溯；另外，返回结果之前，应该恢复`matrix[i*cols + j]`中的内容吧？

[darkTianTian]

@doujiang 我这里其实没有改原参数`matrix`，在主循环中都使用了`list(matrix)`，当然，这样空间复杂度会稍高。

[doujiang]

@darkTianTian 令 M = list(matrix)，查找的字符串为`abcd`，那么匹配到 ab 之后，搜索 b 的方位是右左上下，假设右不匹配 c 返回 False，此时 b 的右边会被修改为'-'，但是返回上一层查找 b 的左时，右边应该恢复原状。

[darkTianTian]

@doujiang 谢谢，我一直以为这么写是对的，其实根本没有恢复。

[doujiang]

@darkTianTian 同学给我看过牛客网的一些题目，感觉它数据很弱，leetcode 更靠谱一些

[darkTianTian]

@doujiang 嗯，确实差很多，我在 LeetCode 上找到这题了。