My dfs C++ solution without breaking original grid


  • 0
    Y
    class Solution {
    public:
        int numIslands(vector<vector<char> > &grid) {
            int m = grid.size();
            if ( m == 0 )
                return 0;
            int n = grid[0].size();
            if ( n == 0 )
                return 0;
            int res = 0;
            vector<unsigned char> visit((m*n + 7)>>3, 0);
            for ( int i = 0; i < m; ++i ) {
                for ( int j = 0; j < n; ++j ) {
                    if ( grid[i][j] == '1' && (visit[(i*n+j)>>3] & (1 << ((i*n+j)&7))) == 0 )
                    {
                        dfs(grid, visit, i, j, m, n);
                        ++res;
                    }
                }
            }
            return res;
        }
    
        void dfs(vector<vector<char> > &grid, vector<unsigned char> &visit, int l, int c, int m, int n) {
            if ( l < 0 || l >= m || c < 0 || c >= n || grid[l][c] == '0' || visit[(l*n+c)>>3] & (1 << ((l*n+c)&7)) )
                return;
            visit[(l*n+c)>>3] |= (1 << ((l*n+c)&7));
            dfs(grid, visit, l-1, c, m, n);
            dfs(grid, visit, l+1, c, m, n);
            dfs(grid, visit, l, c-1, m, n);
            dfs(grid, visit, l, c+1, m, n);
        }
    };

  • 0
    P

    not very familiar with c++, could you explain what do stuff like (ln+c)&7) and (mn + 7)>>3 mean? it looks cool


  • 0
    Y

    (ln+c)&7 means (ln+c)%8
    (mn+7)>>3 means ceil( (mn+7)/8 )


Log in to reply
 

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