深搜法
class Solution {
public:
// 此处必须为static
static const int N = 10;
// 上 左 下 右
int dx[N] = {-1, 0, 1, 0};
int dy[N] = {0, -1, 0, 1};
bool dfs(vector<vector<char>> & matrix, string str, vector<vector<bool>> & used, int ind, int x, int y)
{
if(ind == str.size())
{
return true;
}
else if(x >= matrix.size() || x < 0 || y >= matrix[0].size() || y < 0)
{
return false;
}
else
{
if(used[x][y] == false && matrix[x][y] == str[ind])
{
used[x][y] = true;
for(int i = 0; i < 4; ++ i)
{
if(dfs(matrix, str, used, ind+1, x + dx[i], y + dy[i]))
{
return true;
}
else
{
}
}
used[x][y] = false;
return false;
}
else
{
return false;
}
}
}
bool hasPath(vector<vector<char>>& matrix, string str) {
if(matrix.empty() || matrix[0].empty() || str.empty())
{
return false;
}
else
{
vector<vector<bool>> used(matrix.size(), vector<bool>(matrix[0].size(), false));
for(int i = 0; i < matrix.size(); ++ i)
{
for(int j = 0; j < matrix[i].size(); ++ j)
{
if(dfs(matrix, str, used, 0, i, j))
{
return true;
}
else
{
}
}
}
return false;
}
}
};