DBeach Resort 4R8J-8P (State of Rio Grande.do Norte Brazil), C++ (gcc)

DBeach Resort 4R8J-8P (State of Rio Grande.do Norte Brazil)

/* 27 Finding Ocean
• Leetocde #200 Number of Islands
• Leetocde #305 Number of Islands II 		// union-find 
• Leetocde #694 Number of Distinct Islands
• Leetocde #711 Number of Distinct Islands 	// changing the shape to cadinary
• Leetocde #695 Max area of Islands
• Leetcode #463 Island Perimeter
//
Given: An array of strings where L indicates land and W indicates water, and a coordinate marking a starting point in the middle of the ocean.
Challenge: Find and mark the ocean in the map by changing appropriate Ws to Os.
An ocean coordinate is defined to be the initial coordinate if a W, and
any coordinate directly adjacent to any other ocean coordinate.
void findOcean(String[] map, int row, int column);
String[] map = new String[]{
 "WWWLLLW",
 "WWLLLWW",
 "WLLLLWW"
};
printMap(map); ---> input this 
STDOUT:
WWWLLLW
WWLLLWW
WLLLLWW
findOcean(map, 0, 1); ----> output this 
printMap(map);
STDOUT:
OOOLLLW
OOLLLWW
OLLLLWW
*/

// DFS, or BFS(Queue)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution{
public: 
    // M1: a typical DFS solution 
    void findOcean(vector<string>& map, int i, int j, char oldColor, char newColor) {
        // change from W to O
        int m = map.size();  if(m==0) return; 
        int n = map[0].size();  if(n==0) return ; // corner cases 
        
        if(i<0||j<0 || i>=m || j>=n) return; // over ranges 
        if(map[i][j] != oldColor) return; // must start with water point 
        if(map[i][j] == newColor) return; // already filled 
       
        map[i][j] = 'O';
        int D[4][2] = {{0,1}, {0,-1}, {1,0}, {1,0}};
        for(int k=0; k<4; k++)
            findOcean(map, i+D[k][0], j+D[k][1], oldColor, newColor);
    }
    // M2: BFS, iterative solution 
    void findOcean_BFS(vector<string>& map, int i, int j, char oldColor, char newColor) {
        if(map[i][j] != oldColor || map[i][j] == newColor) return; 
        
        int m = map.size(); if(m==0) return;
        int n = map[0].size(); if(n==0) return; 
        queue<pair<int,int>> q; 
        q.push({i,j});
        while(q.size()){
            auto p = q.front(); q.pop();
            int x = p.first;
            int y = p.second; 
            if(x<0 || y<0 || x>=m || y>=n) continue;
            if(map[x][y] != oldColor || map[x][y] == newColor) continue; 
            map[x][y] = newColor; 
            q.push({x+1, y});
            q.push({x-1, y});
            q.push({x, y+1});
            q.push({x, y-1});
        }
    }
    
    void print(vector<string>& map){
        for(auto x: map)
            cout << x << endl;
        cout << endl;
    }
};

int main() {
    vector<string> map = {
    "WWWLLLW", 
    "WWLLLWW",
    "WLLLLWW"
    };
    
    Solution s; 
    int i= 0, j = 1; 
    s.print(map);
    //s.findOcean(map, i, j, 'W', 'O'); 
    s.findOcean_BFS(map, i, j, 'W', 'O'); 
    s.print(map); 
    
    return 0; 
}


run \| edit \| history \| help	0