題目描述

您將得到一個大小為n x n的正方形地圖,每個地圖的區塊都有一個數值,代表著當地的深度。若一個非邊緣區塊的相鄰區塊之深度值比該區塊還要小,則稱該區塊是一個洞。兩個區塊若有一個共同的邊,則稱它們是相鄰的。



您必須找到所有地圖上的洞,並將它們標示為「X」。

原題網址

https://www.hackerrank.com/challenges/cavity-map

輸入格式

輸入第一行為一個整數n,表示地圖的大小,範圍在1到100之間(包含1和100)。接下來的n行,每行包含n個1到9(包含1和9)的正整數,表示對應區塊的深度。

輸出格式

輸出為n行用「X」標示為洞的區塊之後的地圖結果。

範例輸入

4
1112
1912
1892
1234

範例輸出

1112
1X12
18X2
1234

額外解釋

兩個深度為9的區塊符合洞的條件,因此被取代為「X」。

解題概念

首先尋找符合洞的條件的區塊,在這題目中只需要以非邊緣區塊為中心,判斷其上、下、左、右四個區塊的深度值和中心區塊的深度值之大小即可,如果中心區塊的深度值都比上、下、左、右區塊還小,那這個中心區塊便是一個洞。

最後再將地圖中找出來為洞的位置取代成「X」。

參考答案

import java.util.HashSet;
import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        final int n = Integer.parseInt(sc.nextLine());
        final int n_dec = n - 1;
        final char[][] map = new char[n][n];
        for (int i = 0; i < n; ++i) {
            map[i] = sc.nextLine().toCharArray();
        }
        final HashSet<Integer> caveList = new HashSet<>();
        for (int i = 1; i < n_dec; ++i) {
            final int i_dec = i - 1;
            final int i_enc = i + 1;
            for (int j = 1; j < n_dec; ++j) {
                final int j_dec = j - 1;
                final int j_enc = j + 1;
                final char c = map[i][j];
                if (map[i_dec][j] < c && map[i][j_dec] < c && map[i_enc][j] < c && map[i][j_enc] < c) {
                    caveList.add(i * n + j);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                final int index = i * n + j;
                if (caveList.contains(index)) {
                    System.out.print('X');
                } else {
                    System.out.print(map[i][j]);
                }
            }
            System.out.println();
        }
    }
}