NC285. 矩阵中的路径
描述
示例1
输入:
[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
输出:
true
示例2
输入:
[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcb"
输出:
false
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-07-10
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix char字符型vector<vector<>>
* @param word string字符串
* @return bool布尔型
*/
bool hasPath(vector<vector<char> >& matrix, string word) {
// write code here
if (word == "") return true;
int m = matrix.size();
int n = m > 0 ? matrix[0].size() : 0;
vector<vector<bool>> memo(m, vector<bool>(n, false));
for (int i = 0; i < m; ++i ) {
for (int j = 0; j < n; ++j ) {
if (hasPath(matrix, memo, word, 0, i, j)) return true;
}
}
return false;
}
bool hasPath(vector<vector<char>>& matrix, vector<vector<bool>>& memo, string word, int index, int i, int j) {
// if (index == word.size()) {
// return true;
// }
if (word[index] != matrix[i][j]) return false;
if (index + 1 == word.size()) {
return true;
}
memo[i][j] = true;
vector<int> direction = {1,0,-1,0,1};
bool res = false;
// 四个方向
for (int k = 0; k < 4; ++k) {
int x = i + direction[k];
int y = j + direction[k + 1];
if (x < 0 || x >= matrix.size()) continue;
if (y < 0 || y >= matrix[0].size()) continue;
if (!memo[x][y]) {
res |= hasPath(matrix, memo, word, index + 1, x, y);
}
if (res) return res;
}
memo[i][j] = false;
return res;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2021-07-18
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix char字符型vector<vector<>>
* @param word string字符串
* @return bool布尔型
*/
bool hasPath(vector<vector<char> >& matrix, string word) {
// write code here
if(matrix.empty() || matrix[0].empty()) return false;
if(word.empty()) return true;
for(int i = 0;i < matrix.size();i++)
{
for(int j = 0;j < matrix[0].size();j++)
{
if(check(matrix,word,i,j,0)) return true;
}
}
return false;
}
bool check(vector<vector<char>>& m,string &word,int x,int y,int index)
{
if(x < 0 || y < 0 || x >= m.size() || y >= m[0].size() || word[index] != m[x][y])
{
return false;
}
if(index + 1 == word.length()) return true;
char ch = m[x][y];//存下当前的字符
m[x][y] = 0;//表示已经访问过，并且访问正确
if(check(m,word,x-1,y,index+1) || check(m,word,x+1,y,index+1)
|| check(m,word,x,y-1,index+1) || check(m,word,x,y+1,index+1))
{
return true;
}
m[x][y] = ch;//表示访问错误，则将原来的字符还原
return false;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2021-06-20
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix char字符型vector<vector<>>
* @param word string字符串
* @return bool布尔型
*/
bool inarea(vector<vector<char> >& matrix, int i, int j) {
return i >=0 && i<matrix.size() && j >=0 && j <matrix[0].size();
}
bool dfs(vector<vector<char> >& matrix, string& word, vector<vector<int> >& visited, int k, int i, int j) {
if (!inarea(matrix, i, j) || visited[i][j]) return false;
if (word[k] == matrix[i][j]) {
if (k == word.size()-1) return true;
visited[i][j] = true;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int d = 0; d < 4; ++d) {
int newi = i + dir[d][0];
int newj = j + dir[d][1];
if (dfs(matrix, word, visited, k+1, newi, newj)) {
return true;
}
}
visited[i][j] = false;
}
return false;
}
bool hasPath(vector<vector<char> >& matrix, string word) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int> > visited(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (dfs(matrix, word, visited, 0, i, j)) {
return true;
}
}
}
return false;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2021-06-15
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix char字符型vector<vector<>>
* @param word string字符串
* @return bool布尔型
*/
bool hasPath(vector<vector<char> >& matrix, string word) {
// write code here
if(word.size()==0 || matrix.size() == 0 || matrix[0].size() == 0){
return false;
}
bool result=false;
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
if(matrix[i][j] == word[0]){
result=findPath(matrix,i,j,word,0);
if(result == true){
return true;
}
}
}
}
return result;
}
bool findPath(vector<vector<char> >& matrix,int row_index,int col_index,string& word,int word_index){
word_index++;
if(word_index == word.size()){
return true;
}
bool result=false;
matrix[row_index][col_index]='-1';
if(col_index-1 >= 0 && matrix[row_index][col_index-1] == word[word_index]){//左
result=findPath(matrix,row_index,col_index-1,word,word_index);
matrix[row_index][col_index]=word[word_index];
if(result == true){
return result;
}
}
if(row_index-1 >= 0 && matrix[row_index-1][col_index] == word[word_index]){//上
result=findPath(matrix,row_index-1,col_index,word,word_index);
matrix[row_index][col_index]=word[word_index];
if(result == true){
return result;
}
}
if(col_index+1 < matrix[0].size() && matrix[row_index][col_index+1] == word[word_index]){//右
result=findPath(matrix,row_index,col_index+1,word,word_index);
matrix[row_index][col_index]=word[word_index];
if(result == true){
return result;
}
}
if(row_index+1 < matrix.size() && matrix[row_index+1][col_index] == word[word_index]){//下
result=findPath(matrix,row_index+1,col_index,word,word_index);
matrix[row_index][col_index]=word[word_index];
if(result == true){
return result;
}
}
matrix[row_index][col_index]=word[word_index-1];
return result;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2021-05-22
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix char字符型vector<vector<>>
* @param word string字符串
* @return bool布尔型
*/
bool dfs(vector<vector<char>>& matrix,int u,int x,int y,string& s){
if(matrix[x][y]!=s[u]){
return false;
}
if(u==s.size()-1){
return true;
}
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
char t=matrix[x][y];
matrix[x][y]='*';
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(a>=0&&a<matrix.size()&&b>=0&&b<matrix[0].size()){
if(dfs(matrix,u+1,a,b,s)){
return true;
}
}
}
matrix[x][y]=t;
return false;
}
bool hasPath(vector<vector<char> >& matrix, string word) {
// write code here
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
if(dfs(matrix,0,i,j,word)){
return true;
}
}
}
return false;
}
};