Minimum Cost to Make at Least One Valid Path in a Grid

• 2020 年 3 月 6 日
• 筆記

题意：从最左上角的点开始，按照格子里规定的方向走，必要时可以改变方向，cost+1。问你能够顺利走到最右下角的最小的cost是多少

题解：我们用贪心的思路，从左上角开始，用BFS 计算每个格子到达时所花费的最小cost。这个方法有点像dijskra算法，区别就是不用去找最小的点，因为在BFS的时候，每一层就是最小的值。

struct Node  {      int x;      int y;      int value;      Node(){}      Node(int x,int y,int value)      {          this->x = x;          this->y = y;          this->value = value;      }  };  class Solution {  public:      int dir[5][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0}};      int vis[105][105];      queue<Node> q;      int n,m;      int minCost(vector<vector<int>>& grid) {            n = grid.size();          m = grid[0].size();          int x=0,y=0;          q.push(Node(0,0,0));          vis[0][0]=1;          find(0,0,0,grid);            int ans;          while(!q.empty())          {              Node term = q.front();              q.pop();              if(term.x == n-1&&term.y==m-1)              {                  ans=term.value;                  break;              }                for(int i=1;i<5;i++)              {                  int xx = term.x + dir[i][0];                  int yy = term.y + dir[i][1];                    if(xx<0||xx>=n||yy<0||yy>=m)                      continue;                  if(vis[xx][yy]==0)                  {                      q.push(Node(xx,yy,term.value+1));                      vis[xx][yy]=1;                      find(xx,yy,term.value+1,grid);                  }              }          }          return ans;        }        void find(int x,int y,int value,vector<vector<int>>& grid)      {          while(1)          {              int xx = x + dir[grid[x][y]][0];              int yy = y + dir[grid[x][y]][1];                if(xx<0||xx>=n||yy<0||yy>=m)                  break;              if(vis[xx][yy]==1)                  break;              vis[xx][yy]=1;              q.push(Node(xx,yy,value));              x=xx;              y=yy;          }      }  };