LeetCode 675. Cut Off Trees for Golf Event

题解

排序+BFS最短路。
思路比较直接吧，按树高顺序依次求之间的最短路径。
注意这次BFS的写法不太一样，不用开等大小矩阵存最短长度。

---

Code

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int cutOffTree(vectorvectorint forest) {
        if(forest.empty()||forest[0].empty()) return 0;
        int n=forest.size(),m=forest[0].size();
        vectorvectorint trees;
        
        for(int i=0;in;i++)
            for(int j=0;jm;j++)
                if(forest[i][j]1)
                    trees.push_back({forest[i][j],i,j});
        
        sort(trees.begin(),trees.end());// default 以第一个排
        int res=0;
        
        int col,row;
        for(int i=0,row=col=0;itrees.size();i++){
            int step = MinStep(forest,row,col,trees[i][1],trees[i][2]);
            if(step0) return -1;
            else res+=step;
            
            row = trees[i][1];
            col = trees[i][2];
        }
        
        return res;
    }    
int MinStep(vectorvectorint forest, int sx,int sy, int ex,int ey){
        
        int n=forest.size();
        int m= forest[0].size();
        vectorvectorbool vis(n,vectorbool(m,false));
        queuepairint,int que;
        que.push({sx,sy});
        vis[sx][sy] = true;
        pairint,int p;
        int tx,ty;
        int step=0;
        if(sx==exsy==ey) return 0;
        while(!que.empty()){
            step++;
            int que_size=que.size();
            while(que_size--){// 一步之外的全部节点 入队
                p=que.front();
                que.pop();  
                for(int i=0;i4;i++){
                    tx = p.first+dx[i];
                    ty = p.second+dy[i];
                    if(tx=0  txn ty=0  tym  !vis[tx][ty]  forest[tx][ty]!=0){
                        if(tx==exty==ey) return step;
                        vis[tx][ty]=true;
                        que.push({tx,ty});
                    }
                }
            }
        }     
        return -1;
    }