Leetcode 1368 使网格图至少有一条有效路径的最小代价

题目描述：

 题解：（https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/solution/shi-wang-ge-tu-zhi-shao-you-yi-tiao-you-xiao-lu-2/）

 AC代码:

int minCost(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
        vector<vector<bool>> vis(n,vector<bool>(m,false));
        typedef pair<int,int> pii;
        vector<vector<int>> dis(n,vector<int>(m,INT_MAX));
        priority_queue<pii,vector<pii>,greater<pii>> que;
        que.push(make_pair(0,0));
        dis[0][0] = 0;
        while(!que.empty())
        {
            pii now = que.top();
            que.pop();
            int x = now.second/m;
            int y = now.second%m;
          
           
            if(vis[x][y]) continue;
            vis[x][y] = true;
          //   cout << x <<" " <<y <<endl;
            for(int i=0;i<4;i++)
            {
                int xx = x + d[i][0];
                int yy = y + d[i][1];
                int new_dis = now.first + (i == (grid[x][y]-1)?0:1);
             
                if( xx < 0 || xx >=n || yy < 0 || yy >= m) continue;
               // cout << new_dis << " " << xx <<" " << yy <<endl;
               
                if(new_dis < dis[xx][yy])
                {
                    dis[xx][yy] = new_dis;
                    que.push(make_pair(new_dis,xx*m+yy));
                }
            } 
        }
        return dis[n-1][m-1];
    }