Leetcode 1391. Check if There is a Valid Path in a Grid (cpp)

题目

解法：BFS

就是个BFS变形。只是要注意，判断下一个位置需不需要入队，必须满足当前位置和下一个位置相互联通，需要双向。这跟普通BFS有区别

class Solution {
    
public:bool hasValidPath(vector<vector<int>>& grid) {
    queue<pair<int,int>> q;q.push({
    0,0});int m = grid.size(), n = grid[0].size();vector<pair<int,int>> dirs{
    {
    0,1},{
    0,-1},{
    -1,0},{
    1,0}};vector<pair<int,int>> dirs_ind{
    {
    0,1},{
    2,3},{
    1,3},{
    0,3},{
    1,2},{
    0,2}};vector<pair<int,int>> curr_dirs;vector<pair<int,int>> next_dirs;vector<vector<int>> visited(m,vector<int>(n,false));visited[0][0] = true;while (!q.empty()){
    pair<int,int> curr = q.front();q.pop();if (curr.first == m-1 && curr.second== n-1){
    return true;}int num = grid[curr.first][curr.second];pair<int,int> ind = dirs_ind[num-1];curr_dirs = {
    dirs[ind.first],dirs[ind.second]};for (auto d:curr_dirs){
    int x = curr.first + d.first;int y = curr.second + d.second;// cout << x << y << endl;if (x>=0 && x<m && y>=0 && y<n && !visited[x][y]){
    int next_num = grid[x][y];pair<int,int> next_ind = dirs_ind[next_num-1];next_dirs = {
    dirs[next_ind.first],dirs[next_ind.second]};// need to see if the neighbor has road connected to the current direction of current cellif ((d.first+next_dirs[0].first==0 && d.second+next_dirs[0].second==0) || (d.first+next_dirs[1].first==0 && d.second+next_dirs[1].second==0)){
    // cout << x << y << endl;q.push({
    x,y});visited[x][y] = true;}}}}return false;}
};