解题思路

这是一道图像处理题，需要计算陆地面积。关键点是：

  1. 输入是一个二维矩阵，0表示水面，1表示陆地
  2. 底部边缘一定是陆地，且陆地是连通的
  3. 需要处理两种特殊情况：
    • 被陆地包围的水域应该算作陆地
    • 不与底部边缘相连的陆地是岛屿，不计入面积

解题步骤：

  1. 从底部边缘开始，使用DFS或BFS遍历所有相连的陆地
  2. 标记所有访问过的陆地
  3. 检查所有被陆地包围的水域，将其转换为陆地
  4. 计算最终的陆地面积

代码

#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');
        }
    }
    
    // 标记外部水域
    for(int i=0; i<n; ++i) {
        if(mp[0][i]!='1') dfs(mp, m, n, '1', '2', 0, i);
    }
    for(int i=1; i<m-1; ++i) {
        if(mp[i][0]!='1') dfs(mp, m, n, '1', '2', i, 0);
        if(mp[i][n-1]!='1') dfs(mp, m, n, '1', '2', i, n-1);
    }
    
    // 计算陆地面积
    printf("%d\n", dfs(mp, m, n, '2', '3', m-1, n-1));
    return 0;
}

import java.util.*;

public class Main {
    static int[][] direct = {{0,1},{1,0},{-1,0},{0,-1}};
    
    static int dfs(char[][] mp, int m, int n, char exculsion, char fill, int stx, int sty) {
        mp[stx][sty] = fill;
        Stack<Integer> stk = new Stack<>();
        stk.push(stx);
        stk.push(sty);
        int cnt = 1;
        
        while(!stk.empty()) {
            sty = stk.pop();
            stx = 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;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        char[][] mp = new char[m][n];
        
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                mp[i][j] = (char)(sc.nextInt() + '0');
            }
        }
        
        // 标记外部水域
        for(int i=0; i<n; ++i) {
            if(mp[0][i]!='1') dfs(mp, m, n, '1', '2', 0, i);
        }
        for(int i=1; i<m-1; ++i) {
            if(mp[i][0]!='1') dfs(mp, m, n, '1', '2', i, 0);
            if(mp[i][n-1]!='1') dfs(mp, m, n, '1', '2', i, n-1);
        }
        
        // 计算陆地面积
        System.out.println(dfs(mp, m, n, '2', '3', m-1, n-1));
    }
}

def dfs(mp, m, n, exculsion, fill, stx, sty):
    mp[stx][sty] = fill
    stk = [(stx, sty)]
    cnt = 1
    direct = [(0,1), (1,0), (-1,0), (0,-1)]
    
    while stk:
        stx, sty = stk.pop()
        for dx, dy in direct:
            next_x = stx + dx
            next_y = sty + dy
            if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
                continue
            if mp[next_x][next_y] != exculsion and mp[next_x][next_y] != fill:
                mp[next_x][next_y] = fill
                stk.append((next_x, next_y))
                cnt += 1
    return cnt

def main():
    m, n = map(int, input().split())
    mp = []
    for _ in range(m):
        mp.append([str(x) for x in input().split()])
    
    # 标记外部水域
    for i in range(n):
        if mp[0][i] != '1':
            dfs(mp, m, n, '1', '2', 0, i)
    
    for i in range(1, m-1):
        if mp[i][0] != '1':
            dfs(mp, m, n, '1', '2', i, 0)
        if mp[i][n-1] != '1':
            dfs(mp, m, n, '1', '2', i, n-1)
    
    # 计算陆地面积
    print(dfs(mp, m, n, '2', '3', m-1, n-1))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：DFS（深度优先搜索）和BFS（广度优先搜索）的组合使用
  • 时间复杂度：，其中 和 是矩阵的行数和列数
  • 空间复杂度：，用于递归栈和访问标记