时间戳

首页 > 解决方案 > TLE 在查找岛屿数 (GFG)

c++ - TLE 在查找岛屿数 (GFG)

问题描述

我在问题中找到了 TLE，找不到该岛。链接到问题 - https://practice.geeksforgeeks.org/problems/find-the-number-of-islands/1/?track=md-graph&batchId=144 我的方法是简单地使用 DFS 并查找组件（土地）从陆地开始计算组件的编号并返回。这是我的代码

#include<bits/stdc++.h>
using namespace std;
bool issafe(int i,int j ,int n,int m, vector<vector<char>>graph)
{
  if(i<0 || i>n-1 || j<0 || j>m-1 || graph[i][j]=='0')
  return false;
  return true;
}
void DFS(int u,int v, vector<vector<char>>& grid,int n,int m,vector<vector<int>>& vis)
{
  static int row[]={-1,0,0,1,-1,-1,1,1 };//up,left,right,down, upper left, upper, right, lower left, lower right;
  static int col[]={0,-1,1,0,-1,1,-1,1 };
  vis[u][v]=1;
  for(int k=0;k<8;k++)
  {
    if(issafe(u+row[k],v+col[k],n,m,grid) && !vis[u+row[k]][v+col[k]] )
    {
      DFS(u+row[k], v+col[k], grid, n, m, vis);
    }
  }
}
int numIslands(vector<vector<char>>& grid)
{
  int n=grid.size(),m=grid[0].size();
  vector<vector<int>>vis(n,vector<int>(m,0));
  int ans=0;
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<m;j++)
    {
      if(vis[i][j]==0 && grid[i][j]!='0')
      {
        DFS(i,j,grid,n,m,vis);
        ans++;
      }
    }
  }
  return ans; 
}

标签： c++

解决方案

一项更改是您不希望有额外的空间来标记已访问或未访问。我们可以grid通过将其标记为 say 来自行完成grid[i][j] = '0'。

class Solution
{
    public:
    //Function to find the number of islands.
     int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0)
            return 0;
        int islands = 0;
        int row = grid.size();
        int col = grid[0].size();
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (grid[i][j] == '1')
                islands += helper(grid, i, j);
            }
        }
        return islands;
    }
    
    int helper(vector<vector<char>>& grid, int i, int j) {
        if (i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j] == '0')
            return 0;
        grid[i][j] = '0';
        helper(grid, i, j-1);
        helper(grid, i, j+1);
        helper(grid, i-1, j);
        helper(grid, i+1, j);
        helper(grid, i+1, j+1);
        helper(grid, i+1, j-1);
        helper(grid, i-1, j+1);
        helper(grid, i-1, j-1);
        return 1;
    }
};

这是岛屿数量的公认版本。

推荐阅读