【剑指】75，矩阵中的路径（找入口，递归上下左右）

ゝ一纸荒年。 2023-07-17 14:01 36阅读 0赞

题目描述  
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

思路：  
一个接口，遍历矩阵中每一个元素找到首字母，然后传入子接口，按照这个点开始走，判断结果。如果false，继续遍历。  
子接口是得知第一个首节点后传入的从这个节点开始遍历，走过的节点需要设置走过。  
进行上下左右的递归。  
【trick】\*\*在传参时，用引用可以减少拷贝构造的时间，\*\*特别是对于复杂对象。在回溯中如果需要进行修改参数，可以用两段修改来包含，如：a\[i\]=1; 操作后； a \[i\] =0; 进行恢复。  
代码：

class Solution { 
    public:
        bool hasPath(char* matrix, int rows, int cols, char* str)
        { 
    		vector<int> flag(cols*rows,0);		//没有走过设置为
    		bool condition=false;
    		for(int i=0;i<rows;i++)
    			for(int j=0;j<cols;j++)
    			{ 
    			condition=ispath(matrix,flag,int i,int j,int rows,int cols);
    			if(condition)
    				break;
    			}
    			return condition;
    	}	
    private:
    bool ispath(char* matrix,vector<char>&flag, int x, int y, char * str, int rows,int cols)
    { 
    	if(x>=rows ||y>=cols ||x<0 ||y<0)
    		return false;
    	if(matrix[x*cols+y]==*str && flag[x*cols+y]!=1)
    	{ 
    		flag[x*cols+y]=1;
    		if(*(str+1)=='\0')
    			return ture;
    		bool t= ispath(matrix,flag, x+1,y,(str+1),rows,cols) ||
    				ispath(matrix,flag, x-1,y,(str+1),rows,cols) ||
    				ispath(matrix,flag, x,y+1,(str+1),rows,cols) ||
    				ispath(matrix,flag, x,y-1,(str+1),rows,cols) ;
    		flag[x*cols+y]=0;
    		return t;
    	}
    	return false;
    }