lc649 不同岛屿的数量(dfs+相对坐标)

﹏ヽ暗。殇╰゛Y 2022-12-07 15:29 101阅读 0赞

给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。

请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。

示例 1：

11000  
11000  
00011  
00011  
给定上图，返回结果 1 。

示例 2：

11011  
10000  
00001  
11011  
给定上图，返回结果 3 。

注意：

11  
1  
和

1  
11  
是不同的岛屿，因为我们不考虑旋转、翻转操作。

### 解法: ###

求岛屿的数量思路很简单,利用DFS算法或者BFS算法就可以了

难点在于怎样判断相同形状的岛屿

我们可以利用相对坐标的方法,即把dfs第一个遍历的点看作原点,其他坐标的绝对坐标减去这个点的坐标就是该点的相对坐标

例如上面的示例2,右上角岛屿的点的相对坐标为(0,0)(0,1) 左下角的点的相对坐标也为(0,0),(0,1),那么这两个岛的面积形状都是相同的,相反,左上角和右下角的岛屿的相对坐标序列不一样,虽然他们的面积相同,但是他们的形状却不一样

把所有岛屿的相对坐标序列用一个set进行维护,去掉重复的序列就可以得到结果了

const int N = 55;
    typedef pair<int,int> PII;  
    class Solution {
    public:
        set<vector<PII>> res;
        vector<PII> tres;
        vector<vector<int>> tempGrid;
        bool vis[N][N];
        int kx[4] = {1,-1,0,0},ky[4] = {0,0,1,-1};
        void dfs(int x,int y,int ox,int oy){    
           vis[x][y] = true;
           tres.push_back({x - ox,y - oy});
           for(int i = 0; i < 4; ++i){
              int tx = x + kx[i],ty = y +ky[i];
              if(tx >= 0 && tx < tempGrid.size() && ty >= 0 && ty < tempGrid[0].size() && !vis[tx][ty] && tempGrid[tx][ty] == 1){
                  dfs(tx,ty,ox,oy);
              }
           }
        }
        
        int numDistinctIslands(vector<vector<int>>& grid) {
            memset(vis,false,sizeof(grid));
            tempGrid = grid;
            for(int i = 0; i < grid.size();++i){
                for(int j = 0; j < grid[i].size();++j){
                    if(!vis[i][j] && tempGrid[i][j]==1){
                         tres.clear();
                         dfs(i,j,i,j);
                         res.insert(tres);  
                    }
                }
            }
            return res.size();
        }
    };