首页 > 试题广场 >

矩阵中的路径

[编程题]矩阵中的路径

热度指数：82133 时间限制：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

算法知识视频讲解

小谷围做题家

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix char字符型二维数组 
 * @param word string字符串 
 * @return bool布尔型
*/
func hasPath( matrix [][]byte ,  word string ) bool {
    n,m:=len(matrix),len(matrix[0])
    vis:=make([][]bool,n)
    for i,_:=range vis{
        vis[i]=make([]bool,m)
    }
    dirs:=[][]int{[]int{0,1},[]int{1,0},[]int{0,-1},[]int{-1,0}}
    var ans bool
    var dfs func(int,int,string)
    dfs=func(i,j int,word string){
        if ans||vis[i][j]||matrix[i][j]!=word[0]{
            return
        }
        vis[i][j]=true
        word=word[1:]
        if len(word)==0{
            ans=true
            return
        }
        for _,dir:=range dirs{
            x,y:=i+dir[0],j+dir[1]
            if x>=0&&x<n&&y>=0&&y<m{
                dfs(x,y,word)
            }
        }
        vis[i][j]=false
    }
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if matrix[i][j]==word[0]{
                dfs(i,j,word)
            }
        }
    }
    return ans
}

发表于 2023-03-04 18:50:16 回复(0)

srcrs

提供个解题思路

package main

import "fmt"

func main() {
	matrix := [][]byte{
		{
			'a', 'b', 'c', 'e',
		},
		{
			's', 'f', 'c', 's',
		},
		{
			'a', 'd', 'e', 'e',
		},
	}
	word := "see"
	result := hasPath(matrix, word)
	fmt.Println(result)
}

func hasPath(matrix [][]byte, word string) bool {
	record := make([][]int, len(matrix))
	for x := 0; x < len(matrix); x++ {
		record[x] = make([]int, len(matrix[0]))
	}
	// write code here
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == word[0] {
				record[i][j] = 1
				result := false
				dfs(matrix, i, j, 1, word, record, &result)
				record[i][j] = 0
				if result {
					return result
				}
			}
		}
	}
	return false
}

func dfs(matrix [][]byte, i, j, k int, word string, record [][]int, result *bool) {
	direction := [][]int{{1, 0}, {-1, 0}, {0, -1}, {0, 1}} // 方向 上下左右

	if k == len(word) { // 成功
		*result = true
	}
	if *result == true || k >= len(word) { // 终止
		return
	}

	for d := 0; d < 4; d++ { // 遍历四个方向
		idn, jdn := i+direction[d][0], j+direction[d][1]
		if idn < 0 || idn >= len(matrix) || jdn < 0 || jdn >= len(matrix[i]) || matrix[idn][jdn] != word[k] || record[idn][jdn] == 1 {
			continue
		}
		record[idn][jdn] = 1
		dfs(matrix, idn, jdn, k+1, word, record, result) // 递归
		record[idn][jdn] = 0                             // 回溯
	}
}

发表于 2022-05-19 00:56:47 回复(0)