咨询Codingame编程题a-mountain-of-a-mole-hill的解题方法

题目要求 #

16x16的区域内有鼹鼠活动，花园围栏在地图上用|、+、-符号标注，鼹鼠丘用小写字母o表示，需要计算花园内共有多少个鼹鼠丘。
规则如下：

• 花园的两道平行围栏不会相邻接触
• 花园区域除鼹鼠丘外均为空白，非花园区域除鼹鼠丘外均为点
• 所有未被围栏封闭、接触地图边界的区域均为非花园区域，围栏永远介于花园与非花园区域之间
• 鼹鼠丘不会出现在围栏上

初始代码 #

import java.util.*;
import java.io.*;
import java.math.*;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution {

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < 16; i++) {
            String line = in.nextLine();
        }

        // Write an answer using System.out.println()
        // To debug: System.err.println("Debug messages...");

        System.out.println("answer");
    }
}

实现思路 #

这道题本质是判断区域连通性，核心逻辑是：所有和地图边界连通的非围栏区域都是非花园区域，剩下的非围栏区域就是花园内部，步骤如下：

1. 把输入的16行字符串存为二维字符数组，方便后续遍历访问
2. 新建一个大小为16*16的布尔数组isOutSide，标记对应位置是否为非花园区域，默认初始值为false
3. 遍历地图的四条边界（第一行、最后一行、第一列、最后一列），如果边界位置的字符不是围栏（不是|、+、-三者之一），就从该点开始做BFS或DFS遍历：
   • 遍历过程中遇到围栏就停止前进
   • 所有能到达的非围栏位置，都标记isOutSide为true
4. 遍历整个16*16的地图，统计所有isOutSide为false、且字符为o的位置数量，就是花园内鼹鼠丘的总数

参考实现代码 #

import java.util.*;
import java.io.*;
import java.math.*;

class Solution {
    // 四个遍历方向：上下左右
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        char[][] grid = new char[16][16];
        boolean[][] isOutSide = new boolean[16][16];
        Queue<int[]> queue = new LinkedList<>();

        // 读入地图
        for (int i = 0; i < 16; i++) {
            String line = in.nextLine();
            for (int j = 0; j < 16; j++) {
                grid[i][j] = line.charAt(j);
                // 边界点且不是围栏，加入队列初始标记为外部
                if ((i == 0 || i == 15 || j == 0 || j == 15) && !isFence(grid[i][j])) {
                    isOutSide[i][j] = true;
                    queue.add(new int[]{i, j});
                }
            }
        }

        // BFS标记所有外部区域
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1];
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                // 坐标合法、不是围栏、未被标记为外部
                if (nx >= 0 && nx < 16 && ny >=0 && ny <16 && !isFence(grid[nx][ny]) && !isOutSide[nx][ny]) {
                    isOutSide[nx][ny] = true;
                    queue.add(new int[]{nx, ny});
                }
            }
        }

        // 统计内部的o的数量
        int count = 0;
        for (int i = 0; i < 16; i++) {
            for (int j = 0; j < 16; j++) {
                if (!isOutSide[i][j] && grid[i][j] == 'o') {
                    count++;
                }
            }
        }

        System.out.println(count);
    }

    // 判断是否是围栏字符
    static boolean isFence(char c) {
        return c == '|' || c == '+' || c == '-';
    }
}

内容的提问来源于stack exchange，提问作者Edgar