Problem: 934. 最短的桥

• 思路
• 解题方法
• 复杂度
• Code

思路

• 基础解题思路：
  • 针对岛问题的解决方法有一种通用的解，就是对 上、下、左、右 各个方向进行查找，判断其是否为 1 ，如果为 1 则改为除 0 和 1 意外的任意数字，以此作为标识。
  • 基础解题代码:

    bool isarea(vector<vector<int >>& grid,int x,int y)
    {
        return (x>=0&&x<grid.size()&&y>=0&&y<grid.size());
    }
    int dfs(vector<vector<int>>& grid,int x,int y)
    {
        if(isarea(grid,x,y)==false)
        {
            return -1;
        }
        if(grid[x][y]!=1)
        {
            return -1;
        }
        grid[x][y]=2;
        dfs(grid,x-1,y);
        dfs(grid,x+1,y);
        dfs(grid,x,y-1);
        dfs(grid,x,y+1);
        return 0;
    }

• 本题解题的思路要在基础之上进行更改便可

解题方法

• 将每个岛的边提取出来，极大的缩小了数据量，然后对这两个岛的边进行逐个遍历，直到找到最小的距离
• 这里使用了 \(set<vector<int >>\) 用来去重，然后后面使用了 \(assign()\) 函数将 \(set<vector<int >>\) 转化回了数组 \(vector<vector<int >>\) 当然也可以直接对 \(set<vector<int >>\) 进行遍历

复杂度

• 时间复杂度:

时间复杂度\(O(n^2)\)

• 空间复杂度:

空间复杂度\(O(n)\)

Code

class Solution {
private:
    set<vector<int>> bx;
    set<vector<int>> cx;
    int counts=0;
    bool isarea(vector<vector<int >>& grid,int x,int y)
    {
        return (x>=0&&x<grid.size()&&y>=0&&y<grid.size());
    }
    int dfs(vector<vector<int>>& grid,int x,int y)
    {
        if(isarea(grid,x,y)==false)
        {
            return -1;
        }
        if(grid[x][y]==0)
        {
            return -1;
        }
        if(grid[x][y]==2)
        {
            return 1;
        }
        grid[x][y]=2;
        int x1,x2,x3,x4;
        x1=dfs(grid,x-1,y);
        x2=dfs(grid,x+1,y);
        x3=dfs(grid,x,y-1);
        x4=dfs(grid,x,y+1);
        if(x1==-1||x2==-1||x3==-1||x4==-1)
        {
            vector<int > ax;
            ax.push_back(x);
            ax.push_back(y);
            if(counts==0)
            {
                bx.insert(ax);
            }
            else
            {
                cx.insert(ax);
            }  
        }
        return 0;
    }
public:
    int shortestBridge(vector<vector<int>>& grid) {
        int n=grid.size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    dfs(grid,i,j);
                    counts++;
                }
            }
        }
        int lengths=20001;
        vector<vector<int >> bxx;
        vector<vector<int >> cxx;
        bxx.assign(bx.begin(),bx.end());//用assign实现set转vector
        cxx.assign(cx.begin(),cx.end());
        for(int i=0;i<bxx.size();i++)
        {
            printf("%d %d\n",bxx[i][0],bxx[i][1]);
        }
        printf("\n");
        for(int j=0;j<cxx.size();j++)
        {
            printf("%d %d\n",cxx[j][0],cxx[j][1]);
        }
        for(int i=0;i<bxx.size();i++)
        {
            for(int j=0;j<cxx.size();j++)
            {
                lengths=min(abs(bxx[i][0]-cxx[j][0])+abs(bxx[i][1]-cxx[j][1])-1,lengths);
            }
        }
        return lengths;
    }
};