Problem
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 surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
题意
给出一个0-1矩阵，1代表陆地，0代表水。相连的1可被看作一块陆地。求陆地的数量。
分析
这道题有点迷宫类题目的感觉，而且既然是要遍历所有相连的1，自然考虑通过BFS或DFS算法来遍历所有的1，访问过某点后，将其标记为“已访问”或“不可达”即可。下面分别给出BFS和DFS的实现思路及代码。
BFS
由于题目中要确定一块岛屿（或陆地）是需要遍历上下左右四个方向的，所以第一时间想到的是BFS而不是DFS（有点智障的笔者甚至觉得DFS是不满足要求的）。
与常规的迷宫题不同，在迷宫题中，是有一个明确的终点，BFS或DFS的终止条件就是当前访问的点满足一定条件；然而本题中，并无这个限制，只要将所有未访问且可连通的值为“1”的点遍历即可。
首先是对矩阵的遍历，当遍历至一个未访问且值为“1”的点时，从该点开始进行BFS。在BFS函数中，访问过该点则将其标记为“已访问”（在示例代码中笔者是声明了一个二维bool数组，初始化为false，对应给出的0-1矩阵的每个点，访问过则将其修改为true）。BFS每次结束，都意味着一块陆地被发现，result++.
代码中还要特别注意边界情况的处理。
注意
在实际实现时，笔者犯过一个很严重的错误：
在BFS的具体实现中，笔者起初是先将满足条件的点push进队列，然后在该点为队头时才将其标记为“未访问”。这样的做法可以过一部分测试样例，但是对于一些“1”较密集的矩阵就会超时。笔者对比自己和Discuss中的BFS实现才发现区别就在这个地方。
如果不立即将进入队列的点标记为已访问，则后续相邻的点会将该点再次加入到队列中。具体的Bug过程可以在纸上写一个3*3的全为1的矩阵试验一下。
正确的做法就是在push进队列之后立即修改为“已访问”。
DFS
DFS的应用方法和BFS基本相同，就这道题而言，DFS的代码更加简洁优雅，速度也更快（也可能是笔者的实现繁琐了一些）。
Code
BFS
//Runtime: 9ms
class Solution {
private:
/* Node definition */
struct Node{
int x;
int y;
Node(int ax, int ay){
x = ax;
y = ay;
}
Node(){
x = -1;
y = -1;
}
};
/* Direction */
vector<vector<int> > dir;//Direction
/*************************************
/ ---------------------> y
/ |
/ |
/ |
/ |
/ |
/ |
/ ▼
/ x
/
/*************************************
/* Result Counter */
int result;
/* Marker */
vector<vector<bool> > accessed;
/* BFS */
void _bfs(vector<vector<char> >&A, Node & origin){
queue<Node> q;
q.push(origin);
while(!q.empty()){
//cout << "Now in queue:" << q.size() << endl;
Node tmp(q.front().x, q.front().y);
//accessed[q.front().x][q.front().y] = true;
q.pop();
//cout << "Now in queue:" << q.size() << endl;
for (int i = 0; i < 4; i++){
if (tmp.x + dir[i][0] < 0 || tmp.x + dir[i][0] >= A.size() || tmp.y + dir[i][1] < 0 || tmp.y + dir[i][1] >= A[0].size())
continue;
if ((A[tmp.x + dir[i][0]][tmp.y + dir[i][1]] == '1') && (accessed[tmp.x + dir[i][0]][tmp.y + dir[i][1]] == false)){
q.push(Node(tmp.x + dir[i][0], tmp.y + dir[i][1]));
accessed[tmp.x + dir[i][0]][tmp.y + dir[i][1]] = true;
}
}
}
}
/* Find new origin */
bool _findOriginForBfs(vector<vector<char> >&A){
for (int i = 0; i < A.size(); i++){
for (int j = 0; j < A[0].size(); j++){
if ((A[i][j] == '1') && (accessed[i][j] == false)){
Node tmp(i, j);
_bfs(A, tmp);
result++;
}
}
}
return false;
}
public:
int numIslands(vector<vector<char> >& A) {
/* Initialize Direction */
dir.resize(4);
for (int i = 0; i < 4; i++)
dir[i].resize(2);
/* up */
dir[0][0] = -1;
dir[0][1] = 0;
/* down */
dir[1][0] = 1;
dir[1][1] = 0;
/* right */
dir[2][0] = 0;
dir[2][1] = 1;
/* left */
dir[3][0] = 0;
dir[3][1] = -1;
result = 0;
/* Initialize accessed status */
accessed.resize(A.size());
for (int i = 0; i < A.size(); i++)
accessed[i].resize(A[i].size());
for (int i = 0; i < A.size(); i++)
for (int j = 0; j < A[0].size(); j++)
accessed[i][j] = false;
/* When it breaks, all Node has been visited */
while(_findOriginForBfs(A));
return result;
}
};
DFS
//Runtime: 6ms
class Solution {
private:
void _dfs(vector<vector<char>>& matrix, int x, int y){
if (x < 0 || y < 0 || x >= matrix.size() || y >= matrix[0].size() || matrix[x][y] == '0')
return;
matrix[x][y] = '0';
_dfs(matrix, x + 1, y);
_dfs(matrix, x - 1, y);
_dfs(matrix, x, y - 1);
_dfs(matrix, x, y + 1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int result = 0;
if (grid.size() == 0) return 0;
vector<vector<char>> local = grid;
for (int i = 0; i < local.size(); i++){
for (int j = 0; j < local[0].size(); j++){
if (local[i][j] == '1'){
result++;
_dfs(local, i, j);
}
}
}
return result;
}
};
