[C++] Clean Code - 6 lines


  • 0

    DFS return Island Area

    /**
     * 1. for every '1', DFS or BFS to collect all connected '1's, and mark them as visited;
     * 2. to mark them as visited, we can use a set to collect all visited cell; or we can just mark the label as 'V' in place;
     * Note: Either pre check or post check need to check 2 conditions: in bound & non-visited land('1');
     */
    class Solution {
    public:
        int numIslands(vector<vector<char>>& b) {
            if (!b.size() || !b[0].size())  return 0;
            int m = b.size(), n = b[0].size(), islands = 0;
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    islands += dfs(b, i, j) > 0;
            return islands;
        }
    
    private:
        int dfs(vector<vector<char>>& b, int i, int j) {
            return (i >= 0 && i < b.size() && j >= 0 && j < b[0].size() && b[i][j] == '1') ? b[i][j] = 'v', 1 + dfs(b, i - 1, j) + dfs(b, i + 1, j) + dfs(b, i, j - 1) + dfs(b, i, j + 1) : 0;
        }
    };
    

    DFS return bool (Find a Island)

    class Solution {
    public:
        int numIslands(vector<vector<char>>& b) {
            if (!b.size() || !b[0].size())  return 0;
            int m = b.size(), n = b[0].size(), islands = 0;
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    islands += dfs(b, i, j);
            return islands;
        }
    
    private:
        bool dfs(vector<vector<char>>& b, int i, int j) {
            return i >= 0 && i < b.size() && j >= 0 && j < b[0].size() && b[i][j] == '1' ? b[i][j] = 'v', true | dfs(b, i - 1, j) | dfs(b, i + 1, j) | dfs(b, i, j - 1) | dfs(b, i, j + 1) : false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.