和迷宫问题其实很相似，利用栈的后进先出的思想，采用回溯的方法，记录代码，方便后续回顾。
bool hasPath(char* matrix, int rows, int cols, char* str) { if (matrix == NULL) return false; if (rows == 0 || cols == 0) return false; if (str == NULL) return false; vector<int> position; bool **flag = new bool*[rows];//标记走过的位置 for (int i = 0; i < rows; i++) flag[i] = new bool[cols]; for (int ii = 0; ii < rows; ii++) for (int jj = 0; jj < cols; jj++) flag[ii][jj] = true; for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) { int k = 0; if (matrix[i*cols + j] == str[k]) { position.push_back(i); position.push_back(j); k++; flag[i][j] = false; while (str[k] != '\0' && !position.empty()) { int x = position[position.size() - 2], y = position[position.size() - 1]; if (x > 0 && flag[x - 1][y] && matrix[(x - 1)*cols + y] == str[k])//上 { position.push_back(x - 1); position.push_back(y); k++; flag[x - 1][y] = false; } else if (x < rows - 1 && flag[x + 1][y] && matrix[(x + 1)*cols + y] == str[k])//下 { position.push_back(x + 1); position.push_back(y); k++; flag[x + 1][y] = false; } else if (y > 0 && flag[x][y - 1] && matrix[x*cols + y - 1] == str[k]) { position.push_back(x); position.push_back(y - 1); k++; flag[x][y - 1] = false; } else if (y < cols - 1 && flag[x][y + 1] && matrix[x*cols + y + 1] == str[k]) { position.push_back(x); position.push_back(y + 1); k++; flag[x][y + 1] = false; } else//上下左右均没有符合的字符 { position.pop_back(); position.pop_back(); k--; } } if (!position.empty()) return true; for (int ii = 0; ii < rows; ii++) for (int jj = 0; jj < cols; jj++) flag[ii][jj] = true; } } return false; }主程序测试：
int main() { char*matrix; int rows = 5, cols = 8; matrix = new char[rows*cols]; //char *str = "abcced"; char *str = "SLHECCEIDEJFGGFIE"; char*str2 = "abcb"; matrix= "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS"; cout<<hasPath(matrix, rows, cols,str)<<endl; system("pause"); return 0; }