本题考察的是回溯算法,注意C/C++里面可以定义变量长度的数组,比如
int a = 3;int b = 3;int c[a*b];
。但是如果定义为bool *visited = new bool[rows*cols]
,就是类的类型,是不能用memset(visited, false, sizeof(visited))
初始化的。
C++版本
#include <iostream>
#include <vector>
using namespace std;
bool hasPathCore(char matrix[], int rows, int cols, int row, int col, 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[row*cols+col] = true;
// 往左寻找
bool leftPath = hasPathCore(matrix, rows, cols, row, col-1, str, pathLength, visited);
// 往右寻找
bool rightPath = hasPathCore(matrix, rows, cols, row, col+1, str, pathLength, visited);
// 往上寻找
bool upPath = hasPathCore(matrix, rows, cols, row-1, col, str, pathLength, visited);
// 往下寻找
bool downPath = hasPathCore(matrix, rows, cols, row+1, col, str, pathLength, visited);
hasPath = leftPath || rightPath || upPath || downPath;
// 如果此路不通
if(!hasPath){
pathLength--;
visited[row*cols+col] = false;
}
}
return hasPath;
}
bool hasPath(char matrix[], int rows, int cols, char str[]){
if(matrix == nullptr ||rows < 1 || cols < 1 || str == nullptr)
return false;
bool *visited = new bool[rows*cols];
memset(visited, false, sizeof(visited));
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;
}
int main(){
int a[5] = {1,2,3,4,5};
cout<<&a[2]<<" "<<&a[3]<<endl;
cout<<Fibonacci(6)<<endl;
return 0;
}