200. Number of Islands
Medium
Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
Example 2:
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | vector<vector<int>> dir = {{-1,0},{1,0},{0,-1},{0,1}}; class Solution_dfs { 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 cnt = 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]=='1'){ cnt++; dfs(grid, i, j, m, n); } } } return cnt; } void dfs(vector<vector<char>>& grid, int i, int j, int m, int n){ grid[i][j] = '0'; for(int d=0; d<4; ++d){ int ii = i + dir[d][0]; int jj = j + dir[d][1]; if(ii>=0 && ii<m && jj>=0 && jj<n && grid[ii][jj]=='1'){ dfs(grid, ii, jj, m, n); } } } }; /****/ class Solution_bfs { 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 cnt = 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]=='1'){ cnt++; queue<pair<int, int>> que; que.push(pair<int, int>(i, j)); grid[i][j] = '0'; while(que.size()){ int x = que.front().first; int y = que.front().second; que.pop(); for(int d=0; d<4; ++d){ int x1 = x+dir[d][0]; int y1 = y+dir[d][1]; if(x1>=0 && x1<m && y1>=0 && y1<n && grid[x1][y1]=='1'){ que.push(pair<int, int>(x1, y1)); grid[x1][y1] = '0'; } } } } } } return cnt; } }; /****/ class Solution_union { vector<int> id; int find(int i){ while(id[i]!=i){ i = id[i]; } return i; } void myUnion(int i, int j){ int ri = find(i); int rj = find(j); if(ri<=rj){ id[rj] = ri; }else{ id[ri] = rj; } } 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 N = m*n; id.resize(N); for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ id[i*n+j] = i*n+j; } } for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]=='1'){ for(int d=0; d<4; ++d){ int ii = i+dir[d][0]; int jj = j+dir[d][1]; if(ii>=0 && ii<m && jj>=0 & jj<n && grid[ii][jj]=='1'){ myUnion(i*n+j, ii*n+jj); } } } } } int cnt = 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]=='1' && id[i*n+j]==i*n+j){ cnt++; } } } return cnt; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | class Solution { int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; int m, n; public int numIslands(char[][] grid) { m = grid.length; n = grid[0].length; int ret = 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]=='1'){ ret++; dfs(grid, i, j); } } } return ret; } void dfs(char[][] grid, int i, int j){ for(int[] d : dirs){ int ii = i+d[0], jj = j+d[1]; if(ii>=0 && ii<m && jj>=0 && jj<n && grid[ii][jj]=='1'){ grid[ii][jj]='0'; dfs(grid, ii, jj); } } } } |
Follow up1: count rank 2 islands, where a rank 2 island is an island inside a lake located on a continent. A continent is a piece of land located in the ocean; the ocean is any body of water that touches the edges of the map.
Example:
000000000
000001100
001111100
011000100
001010100
001000100
001111100
000000000
It should return 1.
=============
Follow up2: If the input 2d array is too large to fit in memory, how to handle?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include "head.h" class Solution{ public: int rank2island(vector<vector<char> > &board){ int m = board.size(); if(!m) return 0; int n = board[0].size(); if(!n) return 0; // PrintVV(board, "board: the original board"); queue<pair<int ,int>> que; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(board[i][j]=='0' && (i==0 || j==0 || i==m-1 || j==n-1)){ board[i][j] = '2'; que.push(pair<int, int>(i, j)); } } } while(!que.empty()){ int i = que.front().first, j = que.front().second; que.pop(); bfs(board, i, j, m, n, que, '0', '2'); } // PrintVV(board, "\nboard:set ocean to 2");//2 is ocean for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(board[i][j]=='2'){ bfs(board, i, j, m, n, que, '1', '3'); } } } while(!que.empty()){ int i = que.front().first, j = que.front().second; que.pop(); bfs(board, i, j, m, n, que, '1', '3'); } // PrintVV(board, "\nboard:set continent to 3"); int cnt = 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(board[i][j]=='1') cnt++; } } // cout<<"\nthe number of rank 2 islands is "<<cnt<<endl; return cnt; } void bfs(vector<vector<char>> &board, int i, int j, int m, int n, queue<pair<int, int>> &que, char a, char b){ if(i-1>=0 && board[i-1][j]==a){board[i-1][j]=b; que.push(pair<int, int>(i-1, j));} if(i+1<m && board[i+1][j]==a){board[i+1][j]=b; que.push(pair<int, int>(i+1, j));} if(j-1>=0 && board[i][j-1]==a){board[i][j-1]=b; que.push(pair<int, int>(i, j-1));} if(j+1<n && board[i][j+1]==a){board[i][j+1]=b; que.push(pair<int, int>(i, j+1));} if(i-1>=0 && j-1>=0 && board[i-1][j-1]==a){board[i-1][j-1]=b; que.push(pair<int, int>(i-1, j-1));} if(i-1>=0 && j+1<n && board[i-1][j+1]==a){board[i-1][j+1]=b; que.push(pair<int, int>(i-1, j+1));} if(i+1<m && j-1>=0 && board[i+1][j-1]==a){board[i+1][j-1]=b; que.push(pair<int, int>(i+1, j-1));} if(i+1<m && j+1<n && board[i+1][j+1]==a){board[i+1][j+1]=b; que.push(pair<int, int>(i+1, j+1));} } }; int main(){ vector<vector<char> > board1{{'0','0','0','0','0','0','0','0','0'},\ {'0','0','0','0','0','1','1','0','0'},\ {'0','0','1','1','1','1','1','0','0'},\ {'0','1','1','0','0','0','1','0','0'},\ {'0','0','1','0','1','0','1','0','0'},\ {'0','0','1','0','0','0','1','0','0'},\ {'0','0','1','1','1','1','1','0','0'},\ {'0','0','0','0','0','0','0','0','0'}}; vector<vector<char> > board2{{'0','0','1','0','0','0','0','0','0'},\ {'0','1','1','1','1','1','0','0','0'},\ {'0','1','0','0','0','1','0','0','0'},\ {'0','1','0','1','0','1','0','0','0'},\ {'0','1','0','0','0','1','0','0','0'},\ {'0','1','1','1','1','1','0','0','0'},\ {'0','0','0','0','0','0','0','0','0'},\ {'0','0','0','0','0','0','0','0','0'},\ {'0','1','1','1','1','1','0','0','0'},\ {'0','1','0','0','0','1','0','0','0'},\ {'0','1','0','1','0','1','0','0','0'},\ {'0','1','0','0','0','1','0','0','0'},\ {'0','1','1','1','1','1','0','0','0'},\ {'0','0','0','0','0','0','0','0','0'}}; Solution sol; sol.rank2island(board2); return 0; } |
follow up: 返回每个island的面积。当有被陆地包围的湖泊时，湖泊面积也算在island内。
e.g.
[0,0,0,0,1]
[0,1,1,1,0]
[0,1,0,1,0]
[0,1,1,1,0]
[0,0,0,0,0]
两个island，第一个面积为1，第二个为9.
请问第一题有啥思路吗？我的做法是先遍历一遍，然后把所有的和边界相连的'0‘ 变成 ’*‘， 第二次遍历的时候剩下的'0' 和 '1' 就是岛屿面积。
不知道还有什么更好的方法
我给的也是这个办法。感觉复杂度应该很难提高了。
想问一下楼主第一题下面这三种算不算包围呢? 谢谢 [0,1,0] [1,0,1] [0,1,0] [0,1,1] [1,0,1] [1,1,0] [0,1,1] [1,0,1] [1,1,1] |
算的，相邻按四个方向的来算。
题目问每个岛屿面积分别多少，没想明白被环绕的湖泊面积（环绕的0）怎么算，比如
0 0 0 0 1 0
0 1 1 1 0 1
0 1 0 1 0 1
0 1 1 1 1 0
0 0 0 0 0 0
难道是标完*以后第二次遍历的时候，不管是1还是0 都算同时分别计数0和1的数量？是我想简单了么...
求指教
后头的followup貌似是正题，因为前头那个写的还挺快，但确确实实是正题，scenario不重要，但建议大家要review一下Dijkstra Algorithm。。。回头看了下刷题网竟然没有这个算法在矩阵上头应用的题。。。sooooo good luck
No comments:
Post a Comment