前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination

LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination

作者头像
ShenduCC
发布2019-12-18 17:49:34
5950
发布2019-12-18 17:49:34
举报
文章被收录于专栏:算法修养算法修养

题目

非常简单的BFS 暴搜

代码语言:javascript
复制
struct Node
{
    int x;
    int y;
    int k;
    int ans;
    
    Node(){}
    Node(int x,int y,int k,int ans)
    {
        this->x=x;
        this->y=y;
        this->k=k;
        this->ans=ans;
    }
};
class Solution {
public:
    int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
    int vis[105][105];
    int vis2[105][105];
    int n,m;
    vector<vector<int>> map;
    queue<Node> q;
    int shortestPath(vector<vector<int>>& grid, int k) {
        
        n = grid.size();
        m = grid[0].size();
        memset(vis,-1,sizeof(vis));
        
        q.push(Node(0,0,k,0));
        
        int ans = -1;
        
        while(!q.empty())
        {
            
            Node term = q.front();
            
            q.pop();
            
            if(term.x == n-1 && term.y==m-1)
            {
                return term.ans;
            }
            
            for(int i=0;i<4;i++)
            {
                int xx = term.x +dir[i][0];
                int yy = term.y +dir[i][1];
            
                if(xx < 0 || yy < 0 || xx >= n || yy >=m)
                    continue;
                        
                if(vis[xx][yy]!=-1&&vis[xx][yy]>=term.k)
                    continue;

                if(grid[xx][yy]==1)
                {
                    if(term.k>0)
                    {
                        vis[xx][yy]=term.k-1;
    
                        q.push(Node(xx,yy,term.k-1,term.ans+1));
                    }
                }
                else
                {
                    vis[xx][yy]=term.k;
  
                    q.push(Node(xx,yy,term.k,term.ans+1));
                }

            }
        }
        
        return -1;
        
        
    }
    
    
    
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-12-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档