岛屿周长问题

思路：

flood fill算法算岛屿数量
周长问题只需要在维护岛屿地点的时候，遍历当前点的四周是不是0即可。如果是0则周长 + 1

代码：

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
typedef pair<int,int> PII;

int ans = 0;
const int N = 1010;
int arr[N][N];
bool st[N][N];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};

queue<PII> q;
int n, m;

int get(int x, int y){
    int res = 0;
    for(int i = 0; i < 4; i++){
        int a = x + dx[i];
        int b = y + dy[i];
        if(a < 0 || a >= n || b < 0 || b >= m) res ++;
        if(!arr[a][b]) res ++;
    }
    return res;
}

//遍历岛屿中点的周围 如果是0 则边的个数 + 1
void bfs(int x, int y){
    st[x][y] = true;
    q.push({x, y});
    int res = 0;
    //先算一下起点的边长
    res += get(x, y);
    
    while(q.size()){
        auto t = q.front();
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= n) continue;
            if(arr[a][b] == 1 && !st[a][b]){
                //统计当前点的周长
                res += get(a, b);
                q.push({a, b});
                st[a][b] = true;
            }
        }
    }
    ans = max(ans, res);
}

int main(){
   
    memset(st, 0, sizeof st);
    
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> arr[i][j];
        }
    }
    
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(arr[i][j] == 1 && !st[i][j]){
                bfs(i, j);
            }
        }
    }
    
    cout << ans;
    return 0;
}