首页 > 试题广场 >

矩阵中的路径

[编程题]矩阵中的路径

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

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

示例1

输入

"ABCESFCSADEE",3,4,"ABCCED"

输出

true

示例2

输入

"ABCESFCSADEE",3,4,"ABCB"

输出

false

算法知识视频讲解

Java

加油jptr

效率算不上高，但是代码行数少

    int row=0,col=0;
    public boolean hasPath (String matrix, int rows, int cols, String str) {
        // write code here
        char[] carr=matrix.toCharArray(),carrstr=str.toCharArray();
        char[][] carr2=new char[rows][cols],carr3=new char[rows][cols];
        row=rows;col=cols;
        int count=0;
        for(int i=0;i<rows;i++) for(int j=0;j<cols;j++) carr2[i][j]=carr[count++];
        return findRoud(carr2,carr3,-1,-1,carrstr,0);
    }
    public boolean findRoud(char[][] carr2,char[][] carr3,int x,int y,char[] carrstr ,int k){
        boolean flag=false;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(carr2[i][j]==carrstr[k]&&carr3[i][j]!=1&&((Math.abs(x-i)==1&&y-j==0)||(Math.abs(y-j)==1&&x-i==0)||x==-1)){
                    char[][] tempArr=new char[row][col];
                    for(int m=0;m<row;m++)for(int n=0;n<col;n++)tempArr[m][n]=carr3[m][n];
                    tempArr[i][j]=1;
                    if(k+1<carrstr.length)flag=findRoud(carr2,tempArr,i,j,carrstr,k+1);
                    else flag= true;
                }
            if(flag==true)return true;
            }
        }
        return false;
    }

发表于 2022-06-24 23:10:33 回复(0)

Java

徐MX

    private boolean[][] flags = null;
    public boolean hasPath (String matrix, int rows, int cols, String str) {
        // write code here
        if(matrix.length()<str.length()){return false;}
        char[][] store = new char[rows][cols];
        //标记走过的位置
        flags = new boolean[rows][cols];
        //初始化
        for(int i = 0;i<rows;i++){
            for(int j  = 0;j<cols;j++){
                store[i][j] = matrix.charAt(i*cols+j);
            }
        }
        //遍历
        for(int i = 0;i<store.length;i++){
            for(int j = 0;j<store[i].length;j++){
                if(dfs(store,i,j,str,0)){return true;}
            }
        }
        return false;
        
    }
    //回溯法深度搜索
    public boolean dfs(char[][] store,int x,int y,String str,int curIndex){
       
        //如果x或y超出边界,或者已走过，false
        if(x<0||x>=store.length||y<0||y>=store[x].length||flags[x][y]){return false;}
        //当前字符不相等，false
        if(store[x][y]!=str.charAt(curIndex)){return false;}
         //如果curIndex等于str长度，匹配完毕，true
        if(curIndex == str.length()-1){return true;}
        //设置标志
        flags[x][y]= true;
        curIndex++;
        //分别对右下左上方向进行搜索
        if(dfs(store,x,y+1,str,curIndex)||dfs(store,x+1,y,str,curIndex)||
           dfs(store,x-1,y,str,curIndex)|| dfs(store,x,y-1,str,curIndex)){
            return true;
        }
        
        //退栈，设置为false
        flags[x][y]=false;
        return false;
    }

发表于 2021-10-05 19:42:19 回复(0)

Java

jcldcdmf

算是bfs+dfs吧：

import java.util.*;
public class Solution {
    //用于标记某个位置是否已经在当前路径中
    static int[][] rec;
    static int rowN,colN;
    public boolean hasPath (String matrix, int rows, int cols, String str) {
        // write code here
        rowN = rows;
        colN = cols;
        rec = new int[rows][cols];
        for(int r = 0; r < rows; r ++){
            for(int c = 0; c < cols; c++){
                //找到一个开始位置

                //是否可以从任意一个位置开始遍历呢？即使当前位置的值不等于str.charAt(0)，只要不把这个位置加入到路径中即可，
                //这种思路是错误的，会造成无法标记当前位置，从而导致死循环
                if(matrix.charAt(r * colN + c) == str.charAt(0)){
                    boolean flag = helper(matrix,r,c,str);
                    if(flag){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public static boolean helper(String matrix,int r,int c, String restStr){
        if(restStr.length() == 1){
            return matrix.charAt(r * colN + c) == restStr.charAt(0);
        }
        if(matrix.charAt(r * colN + c) != restStr.charAt(0)){
            return false;
        }
        //防止再次遍历到当前位置
        rec[r][c] = 1;
        if(r - 1 >= 0 && rec[r - 1][c] == 0){
            boolean up = helper(matrix,r - 1,c,restStr.substring(1));
            if(up){
                return true;
            }
        }
        if(r + 1 < rowN && rec[r + 1][c] == 0){
            boolean down = helper(matrix,r + 1,c,restStr.substring(1));
            if(down){
                return true;
            }
        }
        if(c - 1 >= 0 && rec[r][c - 1] == 0){
            boolean left = helper(matrix,r,c - 1,restStr.substring(1));
            if(left){
                return true;
            }
        }
        if(c + 1 < colN && rec[r][c + 1] == 0){
            boolean right = helper(matrix,r,c + 1,restStr.substring(1));
            if(right){
                return true;
            }
        }
        //当一条路径遍历完成之后，可以再次访问当前位置
        rec[r][c] = 0;
        return false;
    }
}

编辑于 2021-07-25 22:45:45 回复(0)

Java

Captain66

典型的回溯题目，一定要熟练

public boolean hasPath(String matrix, int rows, int cols, String str) {
        // write code here
        if (matrix == null || matrix.length() == 0) return false;
        if (str == null || str.length() == 0) return true;
        boolean[][] isUsed = new boolean[rows][cols];// 记录使用过的元素
        for (int i = 0; i < rows; i++) {// 每个位置元素都开始一次
            for (int j = 0; j < cols; j++) {
                if (helper(i, j, 0, matrix, str, isUsed)) return true;
            }
        }
        return false;
    }

    private boolean helper(int row, int col, int curIndex, String matrix, String str, boolean[][] isUsed) {
        // 检查范围、检查是否走过该点，检查是否已经str对应的字符串是否到头
        if (row < 0 || row >= isUsed.length || col < 0 || col >= isUsed[0].length || isUsed[row][col] || curIndex >= str.length())
            return false;
        if (str.charAt(curIndex) == matrix.charAt(row * isUsed[0].length + col)) {
            if (str.length() == curIndex + 1) return true;
            isUsed[row][col] = true;
            boolean result = helper(row - 1, col, curIndex + 1, matrix, str, isUsed);//上
            if (result) return true;// 找到之后就不同向其他方向找，直接退出递归
            result = helper(row + 1, col, curIndex + 1, matrix, str, isUsed);//下
            if (result) return true;
            result = helper(row, col - 1, curIndex + 1, matrix, str, isUsed);//左
            if (result) return true;
            result = helper(row, col + 1, curIndex + 1, matrix, str, isUsed);//右
            if (result) return true;
            isUsed[row][col] = false;// 回溯
        }
        return false;
    }

发表于 2021-03-07 16:31:13 回复(0)