月色与雪色之间
你是第三种绝色
C++，dfs深搜，路径查找。
虽然这是一维的字符数组，但也是可以当做矩阵来操作的。
同样可以借助一个数组int dxy[] = {1, -1, -cols, cols}; 来进行路径遍历，注意因为是一维数组，要遍历到下方字符得“跨行”，其他就是dfs常规操作了。
题目不是很难，直接看代码好了。
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str) {
int size = rows * cols;
vector<bool> vis(size, false);
for (int i = 0; i < size; i++) {
if (matrix[i] == *str) {
vis[i] = true;
if (dfs(matrix, rows, cols, i, str + 1, vis))
return true;
vis[i] = false;
}
}
return false;
}
bool dfs(char *g, const int &rows, const int &cols, int step, char *ptr, vector<bool> &vis) {
int dxy[] = {1, -1, -cols, cols};
if (*ptr == '\0') return true;
for (int i = 0; i < 4; i++) {
int next_step = step + dxy[i];
if (abs(dxy[i]) == 1 && next_step / cols != step / cols)
continue;
if (0 <= next_step && next_step< rows * cols && g[next_step] == *ptr \
&& !vis[next_step]) {
vis[next_step] = true;
if (dfs(g, rows, cols, next_step, ptr + 1, vis))
return true;
vis[next_step] = false;
}
}
return false;
}
};
