526互联

PTA L2-048 寻宝图

发布时间 2023-10-19 21:09:48作者: LH寒酥

目录

PTA L2-048 寻宝图 Flood Fill算法

此题要求出岛屿数量和有宝藏的岛屿数量, 搜索就行

先看前置题目: leetcode 200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0' 或 '1'

解

​ 统计岛屿数量 flood fill

class Solution {
    int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    int res = 0;

    void dfs(char[][] grid, int x, int y) {
        grid[x][y] = '0';
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < grid.length && b >= 0 && b < grid[0].length && grid[a][b] == '1')
                dfs(grid, a, b);
        }
    }

    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < m; j ++ ) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    res += 1;
                }
            }
        }   
        return res; 
    }
}

再看此题解(深搜)

import java.io.*;

public class Main {
    static int islands, treasures, n, m;
    static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    static boolean flag; // flag 判断岛上有没有宝藏

    static void dfs(char[][] grid, int x, int y) {
        if (grid[x][y] != '1') flag = true;
        grid[x][y] = '0';

        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (grid[a][b] != '0') dfs(grid, a, b);
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i ++ ) {
            String str = br.readLine();
            grid[i] = str.toCharArray();
        }
    
        for (int i = 0; i < n; i ++ ) 
            for (int j = 0; j < m; j ++ ) {
                flag = false;
                if (grid[i][j] != '0') {
                    islands++;
                    dfs(grid, i, j);
                    if (flag) treasures++;
                }
            }

        System.out.println(islands + " " + treasures);
    }
}

相关题目

leetcode 463.岛屿的周长

leetcode 695.岛屿的最大面积