leetcode 1036 逃离大迷宫【坐标离散化】

淡淡的烟草味﹌ 2022-10-08 13:26 138阅读 0赞

[题解][Link 1]

题目入栈，还需要继续练习

坐标离散化：大图变小图，因为障碍物很少，
    所以就需要把大块的空地缩小

class Solution { 
    public:
        int n = 1e6;
    
        bool ver(int x){ 
            if(x>=0 && x<n){ 
                return true;
            }
            return false;
        } 
        bool ver(int x,int y){ 
            if(x>=0 && x<n && y>=0 && y<n){ 
                return true;
            }
            return false;
        } 
        bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) { 
            vector<int> arrx;
            vector<int> arry;
            
            for(int k=-1;k<=1;++k){ 
                for(auto b:blocked){ 
                    if(ver(b[0]+k)){ 
                        arrx.push_back(b[0]+k);
                    }
                    if(ver(b[1]+k)){ 
                        arry.push_back(b[1]+k);
                    }
                }
                if(ver(source[0]+k)){ 
                    arrx.push_back(source[0]+k);
                }
                if(ver(source[1]+k)){ 
                    arry.push_back(source[1]+k);
                }
    
                if(ver(target[0]+k)){ 
                    arrx.push_back(target[0]+k);
                }
                if(ver(target[1]+k)){ 
                    arry.push_back(target[1]+k);
                }
            }
    
            sort(arrx.begin(),arrx.end());
            sort(arry.begin(),arry.end());
            arrx.erase(unique(arrx.begin(),arrx.end()),arrx.end());
            arry.erase(unique(arry.begin(),arry.end()),arry.end());
    
            n = max(arrx.size(),arry.size());
            //cout<<n<<endl;
            vector<vector<int>> g(n,vector<int>(n,0));
            for(auto b:blocked){ 
                int x = lower_bound( arrx.begin(),arrx.end(),b[0])-arrx.begin();
                int y = lower_bound( arry.begin(),arry.end(), b[1])-arry.begin();
                g[x][y]=-1;
            }
            
            stack< pair<int,int> > st;
            int x = lower_bound( arrx.begin(),arrx.end(),source[0])-arrx.begin();
            int y = lower_bound( arry.begin(),arry.end(), source[1])-arry.begin();
    
            st.push( { x,y} );
            g[x][y]=-1;
            int tx = lower_bound( arrx.begin(),arrx.end(),target[0])-arrx.begin();
            int ty = lower_bound( arry.begin(),arry.end(), target[1])-arry.begin();
            g[tx][ty] = 2;
    
            while(!st.empty()){ 
                auto tp = st.top();
                st.pop();
                int x = tp.first;
                int y = tp.second; 
                
                if(x==tx && y==ty){ 
                    return true;
                }
    
                if(ver(x+1,y) && g[x+1][y]!=-1){ 
                    st.push({ x+1,y});
                    g[x+1][y]=-1;
                }
                 
                if(ver(x-1,y) && g[x-1][y]!=-1){ 
                    st.push({ x-1,y});
                    g[x-1][y]=-1;
                }
    
                if(ver(x,y+1) && g[x][y+1]!=-1){ 
                    st.push({ x,y+1});
                    g[x][y+1]=-1;
                }
    
                if(ver(x,y-1) && g[x][y-1]!=-1){ 
                    st.push({ x,y-1});
                    g[x][y-1]=-1;
                }
                
            }
            return false;
            
        }
    };

![在这里插入图片描述][20210621203208648.png]

[Link 1]: https://leetcode-cn.com/problems/escape-a-large-maze/solution/c-zuo-biao-chi-san-hua-ti-jie-by-da-li-wang/
[20210621203208648.png]: /images/20221005/fd07ae14f6164cf8be79a88ef8c9a494.png