解いてみた。「Sランク：島探し」

問題

「Sランク：島探し」

コード

Javaで解いてみました。

import java.util.*;

class Pair {
    public int x;
    public int y;
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Map {
    public static final boolean EMPTY = false;
    public static final boolean LAND = true;
    
    public int nN;
    public int nM;
    public boolean[][] bMap;
    
    public Map(int x, int y) {
        nN = x;
        nM = y;
        bMap = new boolean[nN+2][nM+2];
    }
    
    public void set(int x, int y, boolean b) {
        bMap[x][y] = b;
    }
    
    public boolean get(int x, int y) {
        return bMap[x][y];
    }
}

public class Main {
    private static int nN = 0;
    private static int nM = 0;
    
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        nN = sc.nextInt();
        nM = sc.nextInt();
        
        // マップ作成
        Map map = new Map(nN, nM);
        for (int y = 1; y <= nM; y++) {
            for (int x = 1; x <= nN; x++) {
                int nTmp = sc.nextInt();
                map.set(x, y, (nTmp == 1));
            }
        }
 
        // 島探索
        int nLands = 0;
        for (int y = 1; y <= nM; y++) {
            for (int x = 1; x <= nN; x++) {
                if (map.get(x, y) == Map.EMPTY) {
                    continue;
                }

                nLands++;                
                Stack<Pair> stPairs = new Stack<Pair>();
                
                map.set(x, y, Map.EMPTY);
                stPairs.push(new Pair(x, y));
                
                while (!stPairs.empty()) {
                    Pair p = stPairs.pop();    
                    // 左
                    if (map.get(p.x-1, p.y) == Map.LAND) {
                        map.set(p.x-1, p.y, Map.EMPTY);
                        stPairs.push(new Pair(p.x-1, p.y));
                    }
                    // 右
                    if (map.get(p.x+1, p.y) == Map.LAND) {
                        map.set(p.x+1, p.y, Map.EMPTY);
                        stPairs.push(new Pair(p.x+1, p.y));
                    }
                    // 上
                    if (map.get(p.x, p.y-1) == Map.LAND) {
                        map.set(p.x, p.y-1, Map.EMPTY);
                        stPairs.push(new Pair(p.x, p.y-1));
                    }
                    // 下
                    if (map.get(p.x, p.y+1) == Map.LAND) {
                        map.set(p.x, p.y+1, Map.EMPTY);
                        stPairs.push(new Pair(p.x, p.y+1));
                    }
                }
            }
        }       
        
        // 結果出力
        System.out.println(nLands);
    }
}

解説

クラスの説明

class Pair

x座標、y座標を組みにして管理するためのクラスです。

class Map

島の配置を管理するクラスです。

標準入力からの数値の読み取り

Scanner インスタンスを作り、nextInt()メソッドで数値を取得しています。

地図の作成

Map　インスタンスを作り、set() メソッドで配置を行います。陸（黒マス）は Map.LAND, 他（白マス）は Map.EMPTY を設定します。

島の探索

スタート地点の候補として、マップの左上からX方向に、右端に着いたら、Y方向に１増やして、再びX方向に探索を行います。スタート地点が Map.EMPTY ならば、何もしないで次に進みます。

ある島の範囲を探索

まず、スタート地点を Map.EMPTY で更新し、スタックに座標ペアを push() します。

上下左右の探索

スタックから pop() した座標の、上下左右を調べます。

• Map.EMPTY なら何もしません
• Map.LAND なら、Map.EMPTY に更新して、座標ペアをスタックにpush() します

こうして、行ける範囲を探索します。スタックが空になったら、1つの島の探索が終了したことを示します。