剑指offer_矩阵中的路径

小灰灰 2022-06-08 22:48 165阅读 0赞

/*
    请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
    路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
    如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 
    例如 
    a b c e
    s f c s
    a d e e 
    矩阵中包含一条字符串"bcced"的路径，
    但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
    
    剑指offer：回溯法，
    路径可以被看做是一个栈，当在矩阵中定位了路径中前n个字符后，
    在第n个字符周围对应的格子都没有找到第n+1个字符，此时需要回到第n-1个字符，重新定位第n个字符
    
    class  HasPath
    {
    	public static boolean hasPath(char[] matrix, int rows, int cols, char[] str)
        {
    		if (matrix==null||str==null||rows<=0||cols<=0)
    		{
    			return false;
    		}
    
    		boolean[] visited=new boolean[rows*cols];
    		int strIndex=0;
    		for (int matrixIndex=0; matrixIndex<matrix.length; matrixIndex++)
    		{
    			if (hasPathCore(matrix, rows, cols, matrixIndex, str, strIndex, visited))
    			{
    				return true;
    			}
    		}
    
    		return false;
    	}
    		
    	public static boolean hasPathCore(char[] matrix, int rows, int cols, int matrixIndex, char[] str, int strIndex, boolean[] visited)
    	{
    		if (strIndex==str.length)
    		{
    			return true;
    		}
    
    		boolean hasPath=false;
    
    		if (matrixIndex>=0&&matrixIndex<rows*cols&&matrix[matrixIndex]==str[strIndex]&&visited[matrixIndex]==false)
    		{
    			strIndex++;
    			visited[matrixIndex]=true;
    
    			hasPath=hasPathCore(matrix, rows, cols, matrixIndex-cols, str, strIndex, visited)||
    				hasPathCore(matrix, rows, cols, matrixIndex+cols, str, strIndex, visited)||
    				hasPathCore(matrix, rows, cols, matrixIndex-1, str, strIndex, visited)||
    				hasPathCore(matrix, rows, cols, matrixIndex+1, str, strIndex, visited);
    
    			if (!hasPath)
    			{
    				strIndex--;
    				visited[matrixIndex]=false;
    			}
    		}
    
    		return hasPath;
    	}
    
    	public static void main(String[] args) 
    	{
    		char[] matrix={'a', 'b', 'c', 'e','s', 'f', 'c', 's','a', 'd', 'e', 'e'};
    		char[] str={'b','c','c','e','d'};
    		
    		System.out.println(hasPath2(matrix, 3, 4, str));
    	}
    }