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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2020-03-01

第四题
dp[i][j]表示[0,0]到[i,j]需要的次数
初始化dp[i][j] = i+j
对于每个点做一次BFS
BFS的时候 将下一个点加入队列当且仅当 以当前点为中转点 使得dp值变小了
复杂度O(m*n)

class Solution {
public:
    int dx[5]={0,0,0,1,-1};
    int dy[5]={0,1,-1,0,0};
    int dp[105][105];
    int minCost(vector<vector<int>>& grid) {
        int n=grid.size(),m=grid[0].size();
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)dp[i][j]=i+j;
        queue<pair<int,int>>q;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
        q.push(make_pair(i,j));
        while(!q.empty()){
            auto now = q.front();q.pop();
            int x=now.first,y=now.second;
            for(int k=1;k<=4;k++){
                if(grid[x][y]==k && 0<=x+dx[k] && x+dx[k]<n && 0<=y+dy[k] && y+dy[k]<m && dp[x][y]<dp[x+dx[k]][y+dy[k]]){
                    dp[x+dx[k]][y+dy[k]]=dp[x][y];
                    q.push(make_pair(x+dx[k],y+dy[k]));
                }
                else if(grid[x][y]!=k && 0<=x+dx[k] && x+dx[k]<n && 0<=y+dy[k] && y+dy[k]<m && dp[x][y]+1<dp[x+dx[k]][y+dy[k]]){
                    dp[x+dx[k]][y+dy[k]]= dp[x][y]+1;
                    q.push(make_pair(x+dx[k],y+dy[k]));
                }
            }
        }
        return dp[n-1][m-1];
    }
};
展开全部 21 讨论