Leecode---矩阵中的路径

2019-07-21

题目描述

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

思路：

1
2
3

a b c e
s f c s
a d e e

采用深度优先遍历（dfs），从每个节点开始走，走的方向记为： 上右下左。走过的元素要屏蔽掉，防止再次进入。如果走的过程中一旦与查询字符串 “bcced” 不同就 break 掉。

例如从 a 开始走，与 “bcced” 第一个字符不同，直接break
再从 b 开始走，上右下左，只有右能走通，b => c
然后 c 再上右下左，只能下方向走通 b=>c=>c
以此类推，注意上右下左走的时候
1. 数组要有越界判断
2. 已经走过的字符要屏蔽掉

C++ 代码

class Solution{
public:
	bool hasPath(char *matrix, int rows, int cols, char *str)
	{	
		for(int i = 0; i < rows; i++)
			for(int j = 0; j < cols; j++)
				if(dfs(matrix, str, 0, i, j, rows, cols)) //从第 0 个字符开始对比
					return true;
		return false;
	}
	bool dfs(char *matrix, char *str, int u, int x , int y, int rows, int cols) //u--当前第几个字符
	{
		if(matrix[x*cols+y]!=str[u]) return false;
		if(u==strlen(str)-1) return true; //u移动到字符串的长度还没停止，说明查找到
		int t = matrix[x*cols+y];
		matrix[x*cols+y] = '*'; //屏蔽掉已经走过的字符
		int dx[4] = {-1,0,1,0}; //四个方向上右下左x坐标的变化
		int dy[4] = {0,1,0,-1}; //四个方向上右下左y坐标的变化
		for(int i = 0; i < 4; i++){
			int a = x + dx[i], b = y + dy[i];
			if(a>=0 && a<rows && b>=0 && b<cols)
				if(dfs(matrix, str, u+1, a, b, rows, cols))
					return true;
		}
		matrix[x*cols+y] = t;
		return false;
	}
};