[leetcode] 934. Shortest Bridge : https://leetcode.com/problems/shortest-bridge/

Shortest Bridge.cc

class Solution {
public:
    
    int NON_LAND = 0;
    int LAND = 1;
    int ISLAND1 = 2;
    int VISITED = 3;
    
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    
    int row = 0;
    int column = 0;
    
    bool check(int x, int y){
        return 0 <= x && x < row && 0<=y && y < column;
    }
    
    // change 1 -> 2
    void bound_island(vector<vector<int>>& A, int sx, int sy){
        queue<pair<int,int>> q; 
        q.push({sx,sy});
        
        while(!q.empty()){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if(A[x][y] != LAND) continue;
            A[x][y] = ISLAND1;
            
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(!check(nx,ny)) continue;
                if(A[nx][ny] == LAND) q.push({nx, ny});
            }
        }
    }
    
    int getAns(vector<vector<int>>& A, int sx, int sy){
        priority_queue<pair<int,pair<int,int>>> q; //(cnt, (x,y))
        q.push({0, {sx, sy}});
        while(!q.empty()){
            int cnt  = -q.top().first;
            int x = q.top().second.first;
            int y = q.top().second.second;
            q.pop();
            if(A[x][y] == VISITED) continue;
            if(A[x][y] == LAND) return cnt;
            A[x][y] = VISITED;
            
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(!check(nx,ny) || A[nx][ny] == VISITED) continue;
                if(A[nx][ny] == LAND) q.push({-cnt,{nx, ny}});
                else if(A[nx][ny] == ISLAND1) q.push({-cnt,{nx, ny}});
                else if(A[nx][ny] == NON_LAND) q.push({-(cnt+1),{nx, ny}});
            }
        }
        return 0;
    }
    
    int shortestBridge(vector<vector<int>>& A) {
        row = A.size();
        column = A[0].size();
        //BFS
        
        bool setBound = false;
        int sx, sy;
        for(int i=0;i<row;i++){
            for(int j=0;j<column;j++){
                if(A[i][j] == 1){
                    sx = i;
                    sy = j;
                    setBound = true;
                    break;
                }
            }
            if(setBound) break;
        }
        
        bound_island(A, sx, sy);
        return getAns(A, sx, sy);   
    }
};