LeetCode OJ Number of Islands
发布时间：2020-12-13 20:07:04 所属栏目：PHP教程 来源：网络整理
导读：Given a 2d grid map of '1' s (land) and '0' s (water),count 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 su
|
Given a 2d grid map of Example 1: 11110
11010 11000 00000 Answer: 1 Example 2: 11000
11000 00100 00011 Answer: 3
Credits: int R,C;
int dir[4][2] = { 1,⑴,1,⑴ };
bool ** vis;
char ** G;
void dfs(int pi,int pj) {
vis[pi][pj] = true;
int npi,npj;
for (int i = 0; i < 4; i++) {
npi = pi + dir[i][0];
npj = pj + dir[i][1];
if (0 <= npi && npi < R && 0 <= npj && npj < C && !vis[npi][npj] && G[npi][npj] == '1') dfs(npi,npj);
}
}
int numIslands(char **grid,int numRows,int numColumns) {
G = grid;
vis = (bool **)malloc(sizeof(bool*) * numRows);
for (int i = 0; i < numRows; i++) vis[i] = (bool *)malloc(sizeof(bool) * numColumns);
for (int i = 0; i < numRows; i++)
for (int j = 0; j < numColumns; j++) vis[i][j] = false;
int ans = 0;
R = numRows;
C = numColumns;
for (int i = 0; i < numRows; i++)
for (int j = 0; j < numColumns; j++)
if (!vis[i][j] && G[i][j] == '1') {
ans++;
dfs(i,j);
}
for (int i = 0; i < numRows; i++) free(vis[i]);
free(vis);
return ans;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |