讨论/题目交流/🏆 第 178 场力扣周赛/
🏆 第 178 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 有多少小于当前数字的数字
4 分 - 通过投票对团队排名
5 分 - 二叉树中的列表
7 分 - 使网格图至少有一条有效路径的最小代价

妈耶,大神真多,压哨交题。
说下对T4的思路,主要是BFS + DFS。
以样例一举例:grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]],图可以自己看题。
基本思路:
1、每个格子有方向,就代表着,跟着格子路径走所到达的一系列格子的损耗都为0。也就是说该路径上所有格子最小代价都为f. (用DFS做)
2、与该路径相邻的未访问过的格子,其有效路径为f+1. (BFS思想,其一定为最优解)
3、将2所述所有相邻格子入队
4、对队列中每个节点进行1、2、3步操作,直到队列为空. (BFS框架)。

上面第三步比较难处理,即获取路径上所有相邻节点。
我的想法是:用dfs每走到一个格子把它上下左右所有格子都入队。
在出队的时候判断该格子是否访问即可。

ac源代码:

struct node{
    node(int xx,int yy,int ff){
        x =xx;
        y=yy;  
        f=ff;  // 有效路径
    }
  int x,y,f;  
};
class Solution {
public:
    queue<node> que;
    vector<vector<int>> vis;
    int m,n;

    void biao(int x,int y, int f){  // 标记路径相邻格子
        if(x<0|| x >= m)return;
        if(y<0|| y >= n)return;
        que.push( node(x,y,f) );
        return;
    }

    void dfs(int x, int y, vector<vector<int>>& grid, int f){
        // 回溯条件
        if(x<0|| x >= m)return;
        if(y<0|| y >= n)return;
        if(vis[x][y] != -1)return;

        // 访问标记
        vis[x][y] = f;

        // 将上下左右都入队
        biao(x,y+1,f+1);
        biao(x,y-1,f+1);
        biao(x+1,y,f+1);
        biao(x-1,y,f+1);

        if(grid[x][y]==1)dfs(x, y+1, grid,f);
        else if(grid[x][y]==2)dfs(x, y-1, grid,f);
        else if(grid[x][y]==3)dfs(x+1, y, grid,f);
        else if(grid[x][y]==4)dfs(x-1, y, grid,f);    
    }  

    int minCost(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        vis.resize(m);
        for(int i=0;i<m;i++){
            vis[i].resize(n);
            for(int j=0;j<n;j++)vis[i][j]=-1;
        }
        
        que.push(node(0,0,0));
        
       while(!que.empty()){
            node temp = que.front();
            que.pop();
            int x = temp.x;
            int y = temp.y;
            int f = temp.f;
            if(vis[x][y]!=-1)continue;
            dfs(x,y,grid,f);
        }
        return vis[m-1][n-1];
    }
};
2
展开全部 21 讨论