LC 200 Number of Islands
问题描述Given a 2d grid map of? Example 1: Input: 11110 11010 11000 00000 Output:?1 Example 2: Input: 11000 11000 00100 00011 Output: 3 参考答案1 class Solution { 2 public: 3 void foo(vector<vector <char>> &grid,int i,int j){ 4 if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size()) return ; 5 if(grid[i][j] == ‘0‘ ) return; //为了递归准备的停止条件 6 grid[i][j] = ‘0‘; // 为了避免重复,直接将检测过的value归零 7 foo(grid,i-1,j); 8 foo(grid,i+1,j); 9 foo(grid,i,j-1); 10 foo(grid,j+1); 11 12 } 13 14 int numIslands(vector<vector<char>>& grid) { 15 int counter = 0; 16 for(int i = 0; i<grid.size();i++){ 17 for(int j = 0; j<grid[i].size();j++){ 18 if(grid[i][j] == ‘1‘){ 19 counter ++; 20 foo(grid,j); 21 } 22 } 23 } 24 return counter; 25 } 26 }; ? 额外补充SRGA这道题目让我想到了 种子区域生长算法(Seeded Regin Growing Algorithm),参考了一下别人的答案,还真的十分类似。 基本思路是:种下一个种子(遇到的第一个1区域),然后让它生长(递归)。如果是相同区域,就生长(7~10 行),如果不同(4~5行),就停止。 因为区域种子生长是为了,给所有邻接的区域标记label,从而更好识别图象。但这里不需要label,只需要counter。 防止重复由初始点位,开始生长,由于递归规则相同,所以初始点位也会进入递归,为了防止重复,只要被接触的区域,全部重新赋值为0。(6行) 的确是一个很聪明的做法。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |