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

This topic created in 2644 days ago, the information mentioned may be changed or developed.

我个人一般喜欢在 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 友，或者算法大佬帮忙解答一下吗？就是想证明一下自己没有想错。

6 replies 2019-03-24 14:51:13 +08:00

doujiang

Mar 11, 2019

```
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

Mar 11, 2019

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

doujiang

Mar 11, 2019

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

darkTianTian

Mar 23, 2019

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

doujiang

Mar 24, 2019

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

darkTianTian

Mar 24, 2019

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