矩阵中的路径

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix string字符串
# @param rows int整型
# @param cols int整型
# @param str string字符串
# @return bool布尔型
#
class Solution:
    def hasPath(self, matrix, rows, cols, str):
        if len(str) > len(matrix):
            return False
        def judge(matrixs, strs, visited, rows, cols, i, j, k):
            visited_pos = i * cols + j
            if i < 0&nbs***bsp;i >= rows&nbs***bsp;j >= cols&nbs***bsp;visited[i][j] == True&nbs***bsp;matrixs[visited_pos] != strs[k]:
                return False
            if k == len(strs) - 1:
                return True
            visited[i][j] = True
            if judge(matrixs, strs, visited, rows, cols, i + 1, j, k + 1)&nbs***bsp;\
                    judge(matrixs, strs, visited, rows, cols, i - 1, j, k + 1)&nbs***bsp;\
                    judge(matrixs, strs, visited, rows, cols, i, j + 1, k + 1)&nbs***bsp;\
                    judge(matrixs, strs, visited, rows, cols, i, j - 1, k + 1):
                return True
            visited[i][j] = False
            return False

        visited = [[False] * cols for _ in range(rows)]
        for i in range(rows):
            for j in range(cols):
                if judge(matrix, str, visited, rows, cols, i, j, 0):
                    return True
        return False
        # write code here

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

    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;
    }

class Solution:
    # main
    def hasPath(self , matrix : str , rows : int  , cols : int , string : str ):
        #1.special cases
        if len(string)>len(matrix):
            return False
        if len(matrix)!= rows*cols:
            return False
        if rows<0&nbs***bsp;cols<0:
            return False
        
        # 2.construct matrix by string
        matrixList = []
        for i in range(rows):
            matrixList.append(list(matrix[i*cols:i*cols+cols]))
        #print(matrixList)
        
        #3.search the location of the String's first char,which is in the matrixlist
        firstCharAppearIndex = []
        for row in range(rows):
            for col in range(cols):
                if matrixList[row][col]==string[0]:
                    firstCharAppearIndex.append((row,col))
        if len(firstCharAppearIndex)==0:
            return False
        
        #4.Traversal search the sequence,use recursion method
        for idxTuple in firstCharAppearIndex:
            if self.findResultPath(matrixList,idxTuple,string):
                return True
            
        # worst result,cannot find a path then return False
        return False


    def findResultPath(self, matrixList:list , idxTuple:tuple , string:str):
        # idxtuple(row,col) index location of the first character of string,that is string[0]
        # 1.special cases
        if (not 0<=idxTuple[0]<len(matrixList))&nbs***bsp;(not  0<=idxTuple[1]<len(matrixList[0]))&nbs***bsp;\
            (matrixList[idxTuple[0]][idxTuple[1]]!=string[0]):
                return False
        if len(string)==1 and matrixList[idxTuple[0]][idxTuple[1]]==string[0]:
                return True
        # 2.search the surrounding element whether is equal to string[1]
        else:
            matrixList[idxTuple[0]][idxTuple[1]]=""
            res = self.findResultPath(matrixList=matrixList,idxTuple=(idxTuple[0],idxTuple[1]-1),string=string[1:]) \
               &nbs***bsp;self.findResultPath(matrixList=matrixList,idxTuple=(idxTuple[0],idxTuple[1]+1),string=string[1:]) \
               &nbs***bsp;self.findResultPath(matrixList=matrixList,idxTuple=(idxTuple[0]+1,idxTuple[1]),string=string[1:]) \
               &nbs***bsp;self.findResultPath(matrixList=matrixList,idxTuple=(idxTuple[0]-1,idxTuple[1]),string=string[1:]) 
            matrixList[idxTuple[0]][idxTuple[1]]=string[0]
            return res

    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;
    }

import java.util.*;
public class Solution {
    boolean[][] isVisited;
    public boolean hasPath (String matrix, int rows, int cols, String str) {
        if(matrix==null || matrix.length()==0 || 
          rows<1 || cols<1 || cols*rows!=matrix.length() || str.length()>matrix.length()){
            return false;
        }
        isVisited=new boolean[rows][cols];
        char[][] mx=new char[rows][cols];
        char[] cs=str.toCharArray();
        int k=0;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                mx[i][j]=matrix.charAt(k++);
            }
        }
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(dfs(mx,cs,0,i,j)){
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] matrix,char[] cs,int index,int row,int col){
        if(index==cs.length){
            return true;
        }
        if(row<0 || row>=matrix.length || col<0 || col>=matrix[0].length){
            return false;
        }
        if(isVisited[row][col]){
            return false;
        }
        if(matrix[row][col]!=cs[index]){
            return false;
        }
       isVisited[row][col]=true;
       boolean temp=dfs(matrix,cs,index+1,row+1,col) ||
                    dfs(matrix,cs,index+1,row-1,col) ||
                    dfs(matrix,cs,index+1,row,col+1) ||
                    dfs(matrix,cs,index+1,row,col-1);
        isVisited[row][col]=false;
        return temp;
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串 
     * @param rows int整型 
     * @param cols int整型 
     * @param str string字符串 
     * @return bool布尔型
     */
    int rows;
    int cols;
    
    bool hasPath(string matrix, int row, int col, string str) {
        // write code here
        if (str.empty()&&matrix.empty())
            return true;
        if (str.empty())
            return false;
        rows=row;
        cols=col;
        vector<vector<char>> c;
        for(int i=0;i<rows;i++){
            vector<char> b;
            for(int j=0;j<cols;j++){
                b.push_back(0);
            }
            c.push_back(b);
        }
        vector<vector<char>> a;
        int n=0;

        for(int i=0;i<rows;i++){
            vector<char> b;
            for(int j=0;j<cols;j++){
                b.push_back(matrix[n++]);
            }
            a.push_back(b);
        }
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
               if(find(c,a,i,j,str,0))
                   return true;
            }
        }
        return false;
    }
    
    bool find(vector<vector<char>> c,vector<vector<char>> a,int r,int d,string str,int num){
        if(r<0||d<0||r>=rows||d>=cols||num>=str.size()||c[r][d]!=0)
            return false;

        if(a[r][d]==str[num]&&num==str.size()-1)
            return true;
        if (a[r][d]==str[num]){
            c[r][d]++;
            return find(c,a,r-1,d,str,num+1)||find(c,a,r,d-1,str,num+1)
            ||find(c,a,r+1,d,str,num+1)||find(c,a,r,d+1,str,num+1);
        }
        else return false;
    }
 
};

public class Solution {
    //定义了一个函数用来把题目中传入的Sring矩阵转换成二维数组，这样便于理解
    private char[][] changeStrToArray(String matrix, int rows, int cols) {
        char[][] Matrix = new char[rows][cols];
        int count = 0;
        for(int i=0;i<rows; i++)
            for(int j=0;j<cols;j++)
                Matrix[i][j] = matrix.charAt(count++);
        return Matrix;
    }
    //判断该点是不是正确路径的首个点
    private boolean hasPathCore(char[][] Matrix, int rows, int cols, int row, int col, int length, String str, boolean[][] visited) {
        if(length == str.length()) //当创建的路径长度等于目标str的长度后，说明匹配完成，返回true；
            return true;
        boolean hasPath = false;   //首先创建一个boolean变量初始化为false
        if(row >= 0 && row <rows && col >= 0 && col <cols && str.charAt(length) == Matrix[row][col] && visited[row][col] == false ){ //当此时row和col都在范围内且字符等于str上下一个正确字符且该字符还未被加入到路径中时
            length++;              //首先将完成好的路径加1
            visited[row][col]=true;//然后将该点置为已读
            hasPath = hasPathCore(Matrix, rows, cols, row + 1, col, length, str, visited)    
                   || hasPathCore(Matrix, rows, cols, row - 1, col, length, str, visited)
                   || hasPathCore(Matrix, rows, cols, row, col + 1, length, str, visited) 
                   || hasPathCore(Matrix, rows, cols, row, col - 1, length, str, visited);   //将四个可能路径用或逻辑符并起来
            if(!hasPath){          //回溯法的精髓，当目前的点接下来的四个可能路径（上下左右）都无法匹配下一个字符时，说明这个目前的点虽然满足条件，但是接下来不满足条件，所以要回溯这个点（把length减一，并把它的已读状态改回未读，回到上一个点的判断函数里）
                length--;
                visited[row][col] = false;
            }
        }
        return hasPath;
    }
    
    public boolean hasPath (String matrix, int rows, int cols, String str) {
        // 特殊情况
        if(matrix == null || rows < 1 || cols < 1 || str == null)
            return false;
        //状态数组，记录每个点是否已经被加入到路径中，初始未加入为false，已加入为true。
        boolean[][] visited = new boolean[rows][cols];
        char[][] Matrix = changeStrToArray(matrix, rows, cols);
        //循环数组里的每个点，用hasPathCore判断是否能组成正确路径
        for(int row=0;row<rows;row++)
            for(int col=0;col<cols;col++)
                if(hasPathCore(Matrix, rows, cols, row, col, 0, str, visited)) return true;
        return false;
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串 
     * @param rows int整型 
     * @param cols int整型 
     * @param str string字符串 
     * @return bool布尔型
     */
    bool res=0;
    int y=0;
    bool hasPath(string matrix, int rows, int cols, string str) {
        // write code here
        if(str.size()==0)return true;
        y=cols;vector<bool> vis(matrix.size());
        for(int i=0;i<matrix.size();i++)
        {
            string temp;
            if(matrix[i]==str[0])
            {
                temp+=matrix[i];vis[i]=true;
                dfs(matrix,temp,str,i,vis);
                vis[i]=false;
            }
        }
        return res;
    }
    void dfs(string &s,string &temp,string &str,int pos,vector<bool>&vis )
    {
        if(temp==str){res=true;return;}
        int dx[]={-y,y,-1,1};
        for(int i=0;i<4;i++)
        {
            int npos=pos+dx[i];
            if(npos<0||npos>=s.size()||vis[npos])continue;
            if(temp.size()<str.size()&&s[npos]==str[temp.size()])
            {
                temp+=s[npos];
                vis[npos]=true;
                if(temp==str) {
                    res=true;return;
                }
                dfs(s,temp,str,npos,vis);
                vis[npos]=false;
                temp=temp.substr(0,temp.size()-1);
            }
        }
        return ;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串 
     * @param rows int整型 
     * @param cols int整型 
     * @param str string字符串 
     * @return bool布尔型
     */
    bool find_str(int c_rows, int c_cols, int str_index, string str, vector<vector<char>>& matrix_str, vector<vector<bool>>& table)
    {
        int rows = table.size();
        int cols = table[0].size();
        bool result = false;
        char word =  matrix_str[c_rows][c_cols];
        char word_str = str[str_index];
        if (str_index == str.length() - 1 && str[str_index] == matrix_str[c_rows][c_cols])
        {
            result = true;
            return result;
        }
        if(str[str_index] == matrix_str[c_rows][c_cols])
        {
            if (c_rows - 1 >= 0 && !table[c_rows - 1][c_cols])
            {
                table[c_rows - 1][c_cols] = true;
                str_index++;
                result = find_str(c_rows - 1, c_cols, str_index, str, matrix_str, table);
                if(result)
                {
                    return result;
                }
                table[c_rows - 1][c_cols] = false;
                str_index--;
            }
            if (c_rows + 1 < rows && !table[c_rows + 1][c_cols])
            {
                table[c_rows + 1][c_cols] = true;
                str_index++;
                result = find_str(c_rows + 1, c_cols, str_index, str, matrix_str, table);
                if(result)
                {
                    return result;
                }
                table[c_rows + 1][c_cols] = false;
                str_index--;
            }
            if (c_cols - 1 >= 0 && !table[c_rows][c_cols - 1])
            {
                table[c_rows][c_cols - 1] = true;
                str_index++;
                result = find_str(c_rows, c_cols - 1, str_index, str, matrix_str, table);
                if(result)
                {
                    return result;
                }
                table[c_rows][c_cols - 1] = false;
                str_index--;
            }
            if (c_cols + 1 < cols && !table[c_rows][c_cols + 1])
            {
                table[c_rows][c_cols + 1] = true;
                str_index++;
                result = find_str(c_rows, c_cols + 1, str_index, str, matrix_str, table);
                if(result)
                {
                    return result;
                }
                table[c_rows][c_cols + 1] = false;
                str_index--;
            }
        }
        return result;
    }
    bool hasPath(string matrix, int rows, int cols, string str) {
        // write code here
        
        vector<vector<char>> matrix_str(rows, vector<char>(cols));
        int matrix_index = 0;
        for(int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                
                matrix_str[i][j] = matrix[matrix_index];
              
                matrix_index++;
            }
            cout << endl;
        }
        
        bool result = false;
        for(int i = 0; i < rows; i++)
        {
            for(int j = 0; j < cols; j++)
            {
                vector<vector<bool>> table(rows, vector<bool>(cols, false));
                table[i][j] = true;
                result = find_str(i, j, 0, str, matrix_str, table);
                if(result)
                {
                    return result;
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串 
     * @param rows int整型 
     * @param cols int整型 
     * @param str string字符串 
     * @return bool布尔型
     */
    int m,n,visit[1000][1000],ll;
    char mmap[1000][1000];
    string tempstr;
    string sstr;
    int flag = 0;
    void dfs(int x,int y,int l){
       if(x<0||x>=m||y<0||y>=n||l>=ll){
           return;
       }
        if(!visit[x][y]){
            visit[x][y] = 1;
            tempstr += mmap[x][y];
            if(tempstr[l] == sstr[l]){//依次比较每一位，不同就停止
                if(tempstr == sstr){
                    flag = 1;
                    return ;
                }
                l++;
                dfs(x,y+1,l);
                dfs(x+1,y,l);
                dfs(x,y-1,l);
                dfs(x-1,y,l);
            }
            tempstr.pop_back();;
            visit[x][y] = 0;
        }
       return ;
    }
    bool hasPath(string matrix, int rows, int cols, string str) {
        // write code here
        int k = 0;
        ll =  str.length();
        int len = matrix.length();
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                mmap[i][j] = matrix[k++];//把字符地图做好
            }
        }
        memset(visit,0,sizeof(visit));
        m = rows;
        n = cols;
        tempstr = "";
        sstr = str;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dfs(i,j,0);//地图上的每个点作为起点，去找路径。
                if(flag==1)
                    return true;
                tempstr = "";
                memset(visit,0,sizeof(visit));
            }
        }
        return false;
    }
};

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串 
     * @param rows int整型 
     * @param cols int整型 
     * @param str string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (String matrix, int rows, int cols, String str) {
        // write code here
        char[][] board=new char[rows][cols];
        int k=0;
        for(int i=0; i<rows; i++){
            for(int j=0; j<cols; j++){
                board[i][j]=matrix.charAt(k++);
            }
        }
        boolean[][] visited=new boolean[rows][cols];
        for(int i=0; i<rows; i++){
            for(int j=0; j<cols; j++){
                if(dfs(board,i,j,visited,str,0))
                    return true;
            }
        }
        return false;
    }
    private boolean dfs(char[][] board,int i,int j,boolean[][] visited,String str,int k){
        if(i<0 || i>=board.length || j<0 || j>=board[0].length || visited[i][j])
            return false;
        if(board[i][j]!=str.charAt(k))
            return false;
        if(k==str.length()-1)
            return true;
        visited[i][j]=true;
        boolean res=dfs(board,i+1,j,visited,str,k+1) || dfs(board,i-1,j,visited,str,k+1) ||
                dfs(board,i,j+1,visited,str,k+1) || dfs(board,i,j-1,visited,str,k+1);
        visited[i][j]=false;
        return res;
    }
}