首页 > 试题广场 >

矩阵中的路径

[编程题]矩阵中的路径

热度指数：87178 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 $\begin{bmatrix} a & b & c &e \\ s & f & c & s \\ a & d & e& e\\ \end{bmatrix}\quad$ 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

数据范围： $0 \le n,m \le 20\$ , $1\le len \le 25\$

示例1

输入

[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"

输出

true

示例2

输入

[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcb"

输出

false

算法知识视频讲解

Python 3

Vivimore

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:
    def __init__(self):
        # 记录遍历的四个方向
        self.dir = [[1,0],[-1,0],[0,1],[0,-1]]
    def dfs(self, matrix, word, visited, x, y, m):
        # 越界或者已经访问过的
        if x < 0&nbs***bsp;x >= len(matrix)&nbs***bsp;y < 0&nbs***bsp;y >= len(matrix[0])&nbs***bsp;visited[x][y]&nbs***bsp;(matrix[x][y] != word[m]):
            return False
        # m为记录当前第几个字符
        if m == len(word) - 1:
            return True
        # 标记经过的位置
        visited[x][y] = True    
        # 上下左右四个方向搜索
        for k in range(4):
            if self.dfs(matrix, word, visited, x+self.dir[k][0], y+self.dir[k][1], m+1):
                return True
        # 没有找到，退回上一格
        visited[x][y] = False
        return False
        
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # 处理特殊情况
        if len(matrix) == 0:
            return False
        # 初始化visited bool矩阵
        visited = [[False for i in range(len(matrix[0]))] for j in range(len(matrix))]
        m = 0
        for x in range(len(matrix)):
            for y in range(len(matrix[0])):
                # 通过dfs找到路径
                if self.dfs(matrix, word, visited, x, y, m):
                    return True
        return False

发表于 2022-05-04 17:07:13 回复(0)

Python 3

seotamot

回溯就完事了
class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        m, n = len(matrix), len(matrix[0])        
        dirs = [[0,1],[1,0],[-1,0],[0,-1]]
        def dfs(x, y, idx):
            if idx == len(word):
                return True
            if 0 <= x < m and 0 <= y < n and not vis[x][y] and matrix[x][y] == word[idx]:
                vis[x][y] = True
                ans = False
                for dx, dy in dirs:                    
                    ans |= dfs(x+dx, y+dy, idx+1)
                vis[x][y] = False
                return ans
            return False
        
        for i in range(m):
            for j in range(n):
                vis = [[False] * n for _ in range(m)]
                if dfs(i, j, 0):
                    return True
        return False

发表于 2022-03-17 23:20:47 回复(0)

Python 3

哦啦啦啊哦哦

class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        # 看了视频自己写
        m,n=len(matrix),len(matrix[0])
        def dfs(k,i,j):#k是字符串的第几个字符 i，j是第几个格子
            if not 0<=i<m&nbs***bsp;not 0<=j<n&nbs***bsp;word[k]!=matrix[i][j]:# 先把两种特殊情况拿出来
                return False
            if k==len(word)-1:# 把可以结束的情况也拿出来
                return True
            temp=matrix[i][j]
            matrix[i][j]='*'## 这里是为了省内存 所以在替换东西 为了防止在已经走过的路径里边继续瞎跑
            res=dfs(k+1, i-1, j)&nbs***bsp;dfs(k+1, i+1, j)&nbs***bsp;dfs(k+1, i, j-1)&nbs***bsp;dfs(k+1, i, j+1)
            matrix[i][j]=temp
            return res ##就一直判断就行 这里的res只有两种值 要么True 要么False
        for i in range(m):
            for j in range(n):
                if dfs(0, i, j):
                    return True
        return False

b站上一个小姐姐的思路

发表于 2022-03-16 21:20:23 回复(0)

Python 3

kinter1

class Solution:
    def dfs(self, matrix, colors, i, j, strs, target): 
        if i in range(0, len(matrix[:]))  and j in range(0,len(matrix[0][:])):
            if colors[i][j] == 0:
                if strs + matrix[i][j]== target:
                    return True
                elif target.find(strs + matrix[i][j]) == -1: #这里换成 target.find(matrix[i][j]) == -1 会超时
                    return False
                elif len(strs + matrix[i][j]) > len(target):
                    return False
                else:
                    colors[i][j] = 1
                    is_exits = self.dfs(matrix, colors, i - 1, j, strs + matrix[i][j], target)&nbs***bsp;self.dfs(matrix, colors, i + 1, j, strs+ matrix[i][j], target)&nbs***bsp;\
                self.dfs(matrix, colors, i, j - 1, strs+ matrix[i][j], target)&nbs***bsp;self.dfs(matrix, colors, i, j + 1,strs+ matrix[i][j], target)
                    colors[i][j] = 0
                    return is_exits
            else:
                return False
        else:
            return False
    def hasPath(self, matrix: List[List[str]], word: str) -> bool:
        m = len(matrix[:])
        n = len(matrix[0][:])        
        for i in range(m):
            for j in range(n):
                colors = [[0 for _ in range(n)] for _ in range(m)]
                if self.dfs(matrix, colors, i, j, "", word):
                    return True
        return False

注意剪枝操作

发表于 2022-03-07 22:25:24 回复(0)

Python 3

mjw1234

class Solution:
def hasPath(self , matrix: List[List[str]], word: str) -> bool:
# write code here
a=[0]
w=len(matrix[0])
h=len(matrix)
s=[]
def check(l):
b=[]
for i in l:
if not(i[0]>=h or i[0]<0 or i[1]>=w or i[1]<0):
b.append(i)
return b
for i in range(h):#寻找开始位置
for j in range(w):
if matrix[i][j]==word[0]:
s.append([i,j])
if not s:
return False
def tb(s,x,y):#s当前拼接字符串 ls s的长度
if a[0]==1:
return
s.append(matrix[x][y])
matrix[x][y]='*'
if s==list(word):
a[0]=1
return
if s[-1]!=word[len(s)-1]:
return
c=check([[x-1,y],[x+1,y],[x,y+1],[x,y-1]])
for i in c:
cur=matrix[i[0]][i[1]]
tb(s,i[0],i[1])
if a[0]==1:
return
s.pop()
matrix[i[0]][i[1]]=cur
for j in s:
cur=matrix[j[0]][j[1]]
tb([], j[0], j[1])
matrix[j[0]][j[1]]=cur
return a[0]

发表于 2022-02-08 16:07:37 回复(0)

Python 3

Joy_9

class Solution:
    def hasPath(self , board: List[List[str]], word: str) -> bool:
        # write code here
        def dfs(i,j,k):
            if (i<0&nbs***bsp;i>len(board)-1)&nbs***bsp;(j<0&nbs***bsp;j>len(board[0])-1):
                return False
            if board[i][j]!=word[k]:
                return False
            if k==len(word)-1:
                return True
            board[i][j]='/'
            res=dfs(i-1,j,k+1)&nbs***bsp;dfs(i+1,j,k+1)&nbs***bsp;dfs(i,j-1,k+1)&nbs***bsp;dfs(i,j+1,k+1)
            board[i][j]=word[k]
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]==word[0]:
                    if dfs(i,j,0):
                        return True
        return False

发表于 2022-01-27 23:15:30 回复(0)

Python 3

up_zhang

class Solution:
    def hasPath(self, matrix, word: str) -> bool:
        # write code here
        # 1 遍历找到首字母
        # 2，动态规划 找到符合要求的字符串
        def find_word_len(i, j, word, check):
            x = i
            y = j
            word_list = []
            ans_list = []
            word_len = len(word)

            def test(x, y, word_list, ans_list, word, word_len):
                if y < 0&nbs***bsp;y >= len(matrix[0])&nbs***bsp;x < 0&nbs***bsp;x >= len(matrix)&nbs***bsp;len(word) == 0:
                    return
                if matrix[x][y] == word[0]:
                    if len(word_list) + 1 == word_len:
                        ans_list.append(word_list + [matrix[x][y]])
                        return
                    # 左 y>=0
                    if y >= 1 and not check[x][y - 1]:
                        check[x][y - 1] = 1
                        test(x, y - 1, word_list + [matrix[x][y]], ans_list, word[1:], word_len)
                        check[x][y - 1] = 0
                    # 右 y< len(matrix[0])
                    if y <= len(matrix[0]) - 2 and not check[x][y + 1]:
                        check[x][y + 1] = 1
                        test(x, y + 1, word_list + [matrix[x][y]], ans_list, word[1:], word_len)
                        check[x][y + 1] = 0
                    # 上 x >= 0
                    if x >= 1 and not check[x - 1][y]:
                        check[x - 1][y] = 1
                        test(x - 1, y, word_list + [matrix[x][y]], ans_list, word[1:], word_len)
                        check[x - 1][y] = 0
                    # 下 x < len(matrix)
                    if x <= len(matrix) - 2 and not check[x + 1][y]:
                        check[x + 1][y] = 1
                        test(x + 1, y, word_list + [matrix[x][y]], ans_list, word[1:], word_len)
                        check[x + 1][y] = 0

            test(x, y, word_list, ans_list, word, word_len)
            return ans_list

        n = len(matrix)
        m = len(matrix[0])
        check = [[0 for _ in range(m)] for _ in range(n)]
        if not matrix:
            return False
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == word[0]:
                    ans_list = find_word_len(i, j, word, check)
                    if ans_list:
                        return True
        return False

发表于 2022-01-18 21:42:12 回复(0)

Python 3

可恶，被他装到了

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix char字符型二维数组
# @param word string字符串
# @return bool布尔型
#
class Solution:
def hasPath(self , matrix , word ):
if len(word) == 0:
return False
else:
possible_now_point, possible_mat = self.findpath(matrix, word)
if len(possible_now_point) > 0:
return True
else:
return False


def findpath(self , matrix , words):
if len(words) == 1:
possible_now_point, possible_mat = self.where(matrix, words)
return possible_now_point, possible_mat

possible_now_point, possible_mat = self.findpath(matrix, words[1:])
if len(possible_now_point) == 0:
return [],[]
else:
rowmax, colmax = len(matrix)-1, len(matrix[0])-1
possible_now_point_new, possible_mat_new = [], []
for idx,now_point in enumerate(possible_now_point):
now_mat = possible_mat[idx]
up_point = [max(now_point[0]-1,0),now_point[1]]
down_point = [min(now_point[0]+1,rowmax),now_point[1]]
left_point = [now_point[0],max(now_point[1]-1,0)]
right_point = [now_point[0],min(now_point[1]+1,colmax)]
next_points = [up_point,down_point,left_point,right_point]
for next_point in next_points:
if now_mat[next_point[0]][next_point[1]] == words[0]:
possible_now_point_new.append(next_point)
import copy
mat = copy.deepcopy(now_mat)
mat[next_point[0]][next_point[1]] = None
possible_mat_new.append(mat)
return possible_now_point_new, possible_mat_new


def where(self , matrix , word):
possible_mat = [] # 记录可能路径
possible_now_point = [] # 记录可能路径的当前位点
for row_num in range(len(matrix)):
if word in matrix[row_num]:
for col_num, w in enumerate(matrix[row_num]):
if word == w:
import copy
mat = copy.deepcopy(matrix)
mat[row_num][col_num] = None
possible_mat.append(mat)
possible_now_point.append([row_num,col_num])
return possible_now_point, possible_mat

发表于 2021-08-21 18:39:24 回复(0)

Python 3

tantantansq

class Solution:
    def hasPath(self , matrix , word ):
        # write code here
        if len(matrix)==0:
            return False
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.backtrack(matrix, word, 0, i, j) :
                    return True
    
    def backtrack(self,matrix, word, n, i, j):
        '''
        n表示当前对比的是word的第n个字符
        i,j表示当前的坐标
        '''
        if n==len(word):
            return True
        if i<0&nbs***bsp;i>=len(matrix)&nbs***bsp;j<0&nbs***bsp;j>=len(matrix[0])&nbs***bsp;matrix[i][j]!=word[n]:
            return False
        temp=matrix[i][j]
        matrix[i][j]='*'
        if self.backtrack(matrix,word,n+1,i+1,j)&nbs***bsp;self.backtrack(matrix,word,n+1,i-1,j)&nbs***bsp;self.backtrack(matrix,word,n+1,i,j+1)&nbs***bsp;self.backtrack(matrix,word,n+1,i,j-1):
            return True
        matrix[i][j]=temp
        return False

发表于 2021-08-09 01:06:43 回复(0)

Python 3

阿司匹林Yo

class Solution:
    def findPath(self, matrix, i, j, flag, word, index):
        if index == len(word):
            return True
        if i < 0&nbs***bsp;i == len(matrix)&nbs***bsp;j < 0&nbs***bsp;j == len(matrix[0]):
            return False
        if matrix[i][j] != word[index]&nbs***bsp;flag[i*len(matrix[0])+j]:
            return  False
        flag[i*len(matrix[0])+j] = True
        # 向四周搜索
        if self.findPath(matrix, i-1, j, flag, word, index+1)&nbs***bsp;self.findPath(matrix, i+1, j, flag, word, index+1) \
              &nbs***bsp;self.findPath(matrix, i, j-1, flag, word, index+1)&nbs***bsp;self.findPath(matrix, i, j+1, flag, word, index+1):
            return True
        # 恢复路径
        flag[i * len(matrix[0]) + j] = False
        return False

    def hasPath(self, matrix, word):
        if not matrix&nbs***bsp;not word:
            return False
        width, length = len(matrix), len(matrix[0])
        flag = [False] * (width * length)
        # 字符串下标
        for i in range(width):
            for j in range(length):
                if matrix[i][j] == word[0]:
                    if self.findPath(matrix, i, j, flag, word, 0):
                        return True
        return False

发表于 2021-08-04 15:16:55 回复(0)

Python 3

小雨过天阴呀啊啊啊

知识点：回溯 DFS
我为淑女月用Python：QwQ

class Solution:
    def dfs(self, matrix, word, i, j, pos):
        if i < 0 or i == len(matrix) or j < 0 or j == len(matrix[0]) or matrix[i][j] != word[pos]:
            return False
        if pos == len(word) - 1:
            return True
        tmp, matrix[i][j] = matrix[i][j], '.'
        ret = self.dfs(matrix, word, i, j - 1, pos + 1) or self.dfs(matrix, word, i, j + 1, pos + 1) \
              or self.dfs(matrix, word, i - 1, j, pos + 1) or self.dfs(matrix, word, i + 1, j, pos + 1)
        matrix[i][j] = tmp
        return ret

    def hasPath(self, matrix, word):
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.dfs(matrix, word, i, j, 0): # 如果以matrix[i][j]开头找到了一条路径！
                    return True
        return False

发表于 2021-07-18 17:30:03 回复(0)