一.题目
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中间向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
二.思路
这是一个可以用回朔法解决的典型题。首先，在矩阵中任选一个格子作为路径的起点。假设矩阵中某个格子的字符为ch，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程知道路径上的所有字符都在矩阵中找到相应的位置。
由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。
由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。
当矩阵中坐标为（row,col）的格子和路径字符串中下标为pathLength的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下标为pathLength+1的字符。
如果4个相邻的格子都没有匹配字符串中下标为pathLength+1的字符，表明当前路径字符串中下标为pathLength的字符在矩阵中的定位不正确，我们需要回到前一个字符(pathLength-1)，然后重新定位。
一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置
三.代码
bool hasPath(char* matrix,int rows,int cols,char* str){ if(matrix == nullptr || rows <= 0 || cols <= 0 || str == nullptr) return false; bool* visited = new bool[rows*cols]; memeset(visited,0,rows*cols); int pathLength = 0; for(int row = 0;row < rows;row++){ for(int col = 0;col < cols;col++){ if(hasPathCore(matrix,rows,cols,row,col,str,pathLength,visited)){ return true; } } } delete[] visited; return false; } bool hasPathCore(const char* matrix,int rows,int cols,int row,int col,const char*str,int& pathLength,bool* visited){ if(str[pathLength] == ' ') return true; bool hasPath = false; //该点是否符合条件 if(row >= 0 && row < rows && col >= 0 && col < cols &&matrix[row*cols + col] == str[pathLength] &&!visited[row*cols + col]){ ++pathLength; visited[rows*cols + col] = true; //该点周围点是否符合条件 hasPath = hasPathCore(matrix,rows,cols,row,col-1,str,pathLength,visited) ||hasPathCore(matrix,rows,cols,row,col+1,str,pathLength,visited) ||hasPathCore(matrix,rows,cols,row-1,col,str,pathLength,visited) ||hasPathCore(matrix,rows,cols,row+1,col,pathLength,visited); //若否不符合，则清除访问记录 if(!hasPath){ --pathLength; visited[row*cols + col] = false; } } return hasPath; }
四.本题考点
- 考查应聘者对回溯法的理解。通常在二维矩阵上找路径这类问题都可以应用回溯法解决。
- 考查应聘者对数组的编程能力。我们一般都把矩阵看成一个二维的数组。只有对数组的特性充分了解，才有可能快速、正确的实现回溯法的代码。