剑指offer
矩阵中的路径
相似的企业真题
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 64M，其他语言128M
热度指数：434995
本题知识点：
dfs
回溯
算法知识视频讲解
校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
示例1
输入
复制
"ABCESFCSADEE",3,4,"ABCCED"
"ABCESFCSADEE",3,4,"ABCCED"
返回值
复制
true
true
示例2
输入
复制
"ABCESFCSADEE",3,4,"ABCB"
"ABCESFCSADEE",3,4,"ABCB"
返回值
复制
false
false
上一题
登录
/
注册
我的提交
编辑器加载中...
public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { } }
class Solution { public: bool hasPath(char* matrix, int rows, int cols, char* str) { } };
# -*- coding:utf-8 -*- class Solution: def hasPath(self, matrix, rows, cols, path): # write code here
class Solution { public bool hasPath(string matrix, int rows, int cols, string path) { // write code here } }
function hasPath(matrix, rows, cols, path) { // write code here } module.exports = { hasPath : hasPath };
<?php /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ function hasPath( $matrix , $rows , $cols , $path ) { // write code here }
function hasPath(matrix, rows, cols, path) { // write code here }
package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ func hasPath( matrix string , rows int , cols int , path string ) bool { // write code here }
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # @param matrix string字符串 # @param rows int整型 # @param cols int整型 # @param path string字符串 # @return bool布尔型 # class Solution def hasPath(matrix, rows, cols, path) # write code here end end
object Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ def hasPath(matrix: String,rows: Int,cols: Int,path: String): Boolean = { // write code here } }
object Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ fun hasPath(matrix: String,rows: Int,cols: Int,path: String): Boolean { // write code here } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ public boolean hasPath (String matrix, int rows, int cols, String path) { // write code here } }
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ export function hasPath(matrix: string, rows: number, cols: number, path: string): boolean { // write code here }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ func hasPath ( _ matrix: String, _ rows: Int, _ cols: Int, _ path: String) -> Bool { // write code here } }
struct Solution{ } impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param path string字符串 * @return bool布尔型 */ pub fn hasPath(&self, matrix: String, rows: i32, cols: i32, path: String) -> bool { // write code here } }
"ABCESFCSADEE",3,4,"ABCCED"
true
"ABCESFCSADEE",3,4,"ABCB"
false
