C++ 解法, 执行用时: 51ms, 内存消耗: 3676KB, 提交时间: 2020-10-31

#include<bits/stdc++.h>
using namespace std;

const int direct[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};

int dfs(vector<vector<char>>& mp, int m, int n,
        char exculsion, char fill,
        int stx, int sty){
    mp[stx][sty]=fill;
    stack<int> stk;
    stk.push(stx);
    stk.push(sty);
    int cnt = 1;
    while(!stk.empty()){
        sty = stk.top(); stk.pop();
        stx = stk.top(); stk.pop();
        for(int i=0; i<4; ++i){
            int next_x = stx + direct[i][0];
            int next_y = sty + direct[i][1];
            if(next_x<0 || next_x>=m || next_y<0 || next_y>=n){
                continue;
            }
            if(mp[next_x][next_y]!=exculsion && mp[next_x][next_y]!=fill){ // 是陆地
                mp[next_x][next_y] = fill;
                stk.push(next_x);
                stk.push(next_y);
                ++cnt;
            }
        }
    }
    return cnt;
}

int main(){
    int m=0, n=0, cur=0;
    scanf("%d%d", &m, &n);
    vector<vector<char>> mp(m, vector<char>(n, '0'));
    for(int i=0; i<m; ++i){
        for(int j=0; j<n; ++j){
            scanf("%d", &cur);
            mp[i][j] = char(cur+'0');
        }
    }
    // 连通所有海洋，置海洋为 '2'
    int stx=0, sty=0;
    for(int i=0; i<n; ++i){
        sty = i;
        if(mp[stx][sty]!='1'){
            dfs(mp, m, n, '1', '2', stx, sty);
        }
    }
    sty = 0;
    for(int i=1; i<m-1; ++i){
        stx = i;
        if(mp[stx][sty]!='1'){
            dfs(mp, m, n, '1', '2', stx, sty);
        }
    }
    sty = n-1;
    for(int i=1; i<m-1; ++i){
        stx = i;
        if(mp[stx][sty]!='1'){
            dfs(mp, m, n, '1', '2', stx, sty);
        }
    }
    // 把陆地置为3，并计算陆地面积
    stx=m-1, sty=n-1;
    int cnt = dfs(mp, m, n, '2', '3', stx, sty);
    printf("%d\n", cnt);
    return 0;
}

C++ 解法, 执行用时: 56ms, 内存消耗: 4900KB, 提交时间: 2020-12-23

#include<bits/stdc++.h>
using namespace std;

const int direct[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};

int dfs(vector<vector<char>>& mp, int m, int n,
        char exculsion, char fill,
        int stx, int sty){
    mp[stx][sty]=fill;
    stack<int> stk;
    stk.push(stx);
    stk.push(sty);
    int cnt = 1;
    while(!stk.empty()){
        sty = stk.top(); stk.pop();
        stx = stk.top(); stk.pop();
        for(int i=0; i<4; ++i){
            int next_x = stx + direct[i][0];
            int next_y = sty + direct[i][1];
            if(next_x<0 || next_x>=m || next_y<0 || next_y>=n){
                continue;
            }
            if(mp[next_x][next_y]!=exculsion && mp[next_x][next_y]!=fill){ // 是陆地
                mp[next_x][next_y] = fill;
                stk.push(next_x);
                stk.push(next_y);
                ++cnt;
            }
        }
    }
    return cnt;
}

int main(){
    int m=0, n=0, cur=0;
    scanf("%d%d", &m, &n);
    vector<vector<char>> mp(m, vector<char>(n, '0'));
    for(int i=0; i<m; ++i){
        for(int j=0; j<n; ++j){
            scanf("%d", &cur);
            mp[i][j] = char(cur+'0');
        }
    }
    // 连通所有海洋，置海洋为 '2'
    int stx=0, sty=0;
    for(int i=0; i<n; ++i){
        sty = i;
        if(mp[stx][sty]!='1'){
            dfs(mp, m, n, '1', '2', stx, sty);
        }
    }
    sty = 0;
    for(int i=1; i<m-1; ++i){
        stx = i;
        if(mp[stx][sty]!='1'){
            dfs(mp, m, n, '1', '2', stx, sty);
        }
    }
    sty = n-1;
    for(int i=1; i<m-1; ++i){
        stx = i;
        if(mp[stx][sty]!='1'){
            dfs(mp, m, n, '1', '2', stx, sty);
        }
    }
    // 把陆地置为3，并计算陆地面积
    stx=m-1, sty=n-1;
    int cnt = dfs(mp, m, n, '2', '3', stx, sty);
    printf("%d\n", cnt);
    return 0;
}