题解 | #矩阵中的路径# bfs对照版
矩阵中的路径
https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6
#include <queue>
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool find_flag = false;
typedef struct {
int x;
int y;
bool vis[1000][1000];
string str;
} Point;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix char字符型vector<vector<>>
* @param word string字符串
* @return bool布尔型
*/
// const int maxsize =1000;
// void dfs(vector<vector<char> >& matrix,int x, int y, bool vis[1000][1000], int shape_x, int shape_y,string path,const string teststr) {
// if(path == teststr ){
// find_flag =true;
// }
// if (x >= 0 && x < shape_x && y >= 0 && y < shape_y
// &&!vis[x][y]&&teststr.substr(0,path.size())==path) {
// path.push_back(matrix[x][y]);
// vis[x][y] = true;
// cout<<path<<endl;
// for (int i = 0; i < 4; i++) {
// int next_x = x + dx[i];
// int next_y = y + dy[i];
// dfs(matrix,next_x, next_y, vis, shape_x, shape_y,path,teststr);
// }
// vis[x][y ] = false;
// path.pop_back();
// }
// return ;
// }
bool hasPath(vector<vector<char> >& matrix, string word) {
// cout<<matrix.size()<<endl;
// write code here
bool vis[1000][1000] = {false};
queue<Point>que;
// for (int i = 0; i < matrix.size(); ++i) {
// for (int j = 0; j < matrix[i].size(); ++j) {
// dfs(matrix, i, j, vis, matrix.size(), matrix[i].size(),"",word);
// }
// }
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[i].size(); ++j) {
Point tempPoint{i, j,vis,""};
que.push(tempPoint);
}
}
while (!que.empty()) {
Point tempPoint = que.front();
que.pop();
if (tempPoint.x >= 0 && tempPoint.x < matrix.size() && tempPoint.y >= 0 &&
tempPoint.y < matrix[0].size()) {
vis[tempPoint.x][tempPoint.y] = true;
for (int i = 0; i < 4; i++) {
int next_x = tempPoint.x + dx[i];
int next_y = tempPoint.y + dy[i];
Point atempPoint{next_x, next_y};
que.push(atempPoint);
}
vis[tempPoint.x][tempPoint.y] = false;
}
}
return find_flag ? true : false;
}
};
/**
*后面就不太想写了 应该是不断从 当前队列中取vis 数组用于标记，同时在它的string path中添加路径
，如果路径等于teststr，就应该return了，不得不说手动维护vis和path还是很麻烦的。
*/
