LeetCode——200.岛屿数量
程序员文章站
2022-04-07 12:27:20
...
题目
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
深搜思路
一开始本来没什么思路,然后百度了一下,看看这种题型是如何解答的,就是搜到陆地的时候,以该节点为起点,把周围跟他相连接的陆地全部给置为1即可。又一次打败了心魔,本来以前自己看到这种题就觉得害怕,冲冲冲!
代码
class Solution {
//方向数组,右下左上
static int d_x[]={0,1,0,-1};
static int d_y[]={1,0,-1,0};
static int row;
static int colomn;
static int ans;
public int numIslands(char[][] grid) {
if (grid==null || grid.length==0 || grid[0].length==0)
return 0;
ans=0;//岛屿数目
row=grid.length;
colomn=grid[0].length;
for (int i=0;i<row;++i)
for (int j=0;j<colomn;++j)
if (grid[i][j]=='1')
{
++ans;
dfs(i,j,grid);
}
return ans;
}
public static void dfs(int x,int y,char[][]grid)
{
grid[x][y]='0';//把搜索到的点置为0
int temp_x=0;
int temp_y=0;
for (int i=0;i<=3;++i)
{
temp_x=x+d_x[i];
temp_y=y+d_y[i];
if (temp_x>=0 && temp_x<row && temp_y>=0 && temp_y<colomn && grid[temp_x][temp_y]=='1')//陆地
{
dfs(temp_x,temp_y,grid);
}
}
}
}
结果
ac了,这次相比于以往的搜索题,不用有标记数组,一开始以为还是得要,后来发现,标记数组没什么用,就不加了,偷懒,真香!!
广搜思路
进行搜索,搜到1的,就在当前位置进行广搜,把相连的为1的点都加到队列中即可。因为这里开了标记数组,会比较慢一点。
代码
import java.util.LinkedList;
import java.util.Queue;
class Point{
int x;
int y;
}
class Solution {
//方向数组,右下左上
static int d_x[]={0,1,0,-1};
static int d_y[]={1,0,-1,0};
static int row;
static int colomn;
static int ans;// 岛屿数量
static int visited[][];//标记数组
static Queue<Point> queue=new LinkedList();
public int numIslands(char[][] grid) {
if (grid==null || grid.length==0 || grid[0].length==0)
return 0;
ans=0;//岛屿数目
row=grid.length;
colomn=grid[0].length;
queue.clear();
visited=new int[row][colomn];
for (int i=0;i<row;++i) {
for (int j = 0; j < colomn; ++j)
{
visited[i][j]=0;//没有访问过
if (grid[i][j] == '1')
{
++ans;
Point temp = new Point();
temp.x = i;
temp.y = j;
queue.offer(temp);
while (!queue.isEmpty())
{
int a = queue.peek().x; //队首的横坐标
int b = queue.peek().y; //队首的纵坐标
grid[a][b] = '0';//改为水
for (int k = 0; k <= 3; ++k)
{
//队首的四个方向的临时坐标
int temp_a = a + d_x[k];
int temp_b = b + d_y[k];
if (temp_a >= 0 && temp_a < row && temp_b >= 0 && temp_b < colomn && grid[temp_a][temp_b] == '1' && visited[temp_a][temp_b]==0)
{
Point h = new Point();
h.x = temp_a;
h.y = temp_b;
visited[temp_a][temp_b]=1;//访问了
queue.offer(h);
}
}
queue.poll();
}
}
}
}
return ans;
}
}
结果
虽然ac了,可是广搜的时间比深搜的时间还要慢,其实是不应该的。应该是开了标记数组的缘故,看了题解,它那种没有标记数组,挺好的。
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0';
queue<pair<int, int>> neighbors;
neighbors.push({r, c});
while (!neighbors.empty()) {
auto rc = neighbors.front();
neighbors.pop();
int row = rc.first, col = rc.second;
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.push({row-1, col});
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.push({row+1, col});
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.push({row, col-1});
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.push({row, col+1});
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
};
推荐阅读