前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >矩阵中的路径

矩阵中的路径

作者头像
名字是乱打的
发布2021-12-22 15:01:33
1.1K0
发布2021-12-22 15:01:33
举报
文章被收录于专栏:软件工程软件工程
题目描述

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

思路

回溯法: 对于此题,我们需要设置一个判断是否走过的标志数组,长度和矩阵大小相等

我们对于每个结点都进行一次judge判断,且每次判断失败我们应该使标志位恢复原状即回溯

judge里的一些返回false的判断:

  • 如果要判断的(i,j)不在矩阵里
  • 如果当前位置的字符和字符串中对应位置字符不同
  • 如果当前(i,j)位置已经走过了

否则先设置当前位置走过了,然后判断其向上下左右位置走的时候有没有满足要求的.

最后如果上面所有判断都没返回true,则最后恢复原状态

代码语言:javascript
复制
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        int[] flags=new int[matrix.length]; //用1标志走过
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                boolean res = helper(matrix, rows, cols, i, j, 0, str, flags);
                if (res) return true;
            }
        }
        return false;
    }
    //k指当前匹对的字串下标
    public boolean helper(char[]matrix,int rows,int cols,int i,int j,int k,char[]str,int[]flag){
        int curr=i*cols+j;
        if (i<0||i>=rows||j<0||j>=cols||flag[curr]==1||matrix[curr]!=str[k]) return false;
        if (k==str.length-1) return true;

        flag[curr]=1;

        if (helper(matrix,rows,cols,i+1,j,k+1,str,flag)||helper(matrix,rows,cols,i-1,j,k+1,str,flag)||
                helper(matrix,rows,cols,i,j+1,k+1,str,flag)||helper(matrix,rows,cols,i,j-1,k+1,str,flag)
        )return true;

        flag[curr]=0;
        return false;
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/12/16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 思路
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档