题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
class Solution { public: bool f = 0; void dfs(char* matrix, int rows, int cols, char* str, bool* vis, int n, int an) { if(n == strlen(str)) { f = 1; return; } if((an-1>=0)&&(an-1<cols*rows)&&vis[an-1]==0&&str[n]==matrix[an-1]) { vis[an-1] = 1; dfs(matrix, rows, cols, str, vis, n+1, an-1); if(f == 1) return; vis[an-1] = 0; } if((an+1>=0)&&(an+1<cols*rows)&&vis[an+1]==0&&str[n]==matrix[an+1]) { vis[an+1] = 1; dfs(matrix, rows, cols, str, vis, n+1, an+1); if(f == 1) return; vis[an+1] = 0; } if((an-cols>=0)&&(an-cols<cols*rows)&&vis[an-cols]==0&&str[n]==matrix[an-cols]) { vis[an-cols] = 1; dfs(matrix, rows, cols, str, vis, n+1, an-cols); if(f == 1) return; vis[an-cols] = 0; } if((an+cols>=0)&&(an+cols<cols*rows)&&vis[an+cols]==0&&str[n]==matrix[an+cols]) { vis[an+cols] = 1; dfs(matrix, rows, cols, str, vis, n+1, an+cols); if(f == 1) return; vis[an+cols] = 0; } return; } bool hasPath(char* matrix, int rows, int cols, char* str) { bool vis[rows*cols+5]; for(int i=0; i<rows; i++) for(int j=0; j<cols; j++) { int an = i*cols+j; if(matrix[an] == str[0]) { memset(vis, 0, sizeof(vis)); vis[an] = 1; dfs(matrix, rows, cols, str, vis, 1, an); if(f == 1) return 1; } } return 0; } };