ACMの過去問解いてみた！！（5）〜2009年国内予選ProblemB

ProblemB
生まれて初めての再帰…。
島の数を求める問題です。
方針としては、まずインプットの島をそのまま配列に代入します。
それから配列を走査するのですが、島を見つけたらその島の大きさの分だけ再帰して数字を書き換えます。
例えば、最初に見つけた島は1→2に、次に見つけた島は2→3という感じです。
1だけを探していき、終わったらカウントを-1して出力すれば島の数になります。

package acm2009.b;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(Q.class
				.getResourceAsStream("input.txt")));

		String line = null;
		while ((line = br.readLine()) != null) {

ここまではファイルの入出力。

			String[] str = line.split(" ");

			int w = Integer.parseInt(str[0]);     //地図の幅
			int h = Integer.parseInt(str[1]);     //地図の高さ
			int count = 1;　　　　　　　　　 //島を数えるためのカウンタ

			int[][] map = new int[h][w];           //島

			for (int i = 0; i < h; i++) {
				line = br.readLine();
				String[] str2 = line.split(" ");
				for(int j = 0 ; j < w ; j++){
				map[i][j] = Integer.parseInt(str2[j]);
				}
			}

			if (w == 0 && h == 0) {
				break;
			}

ここまでで変数に全て入力します。

			for(int i = 0 ; i < h ; i++){
				for(int j=0 ; j < w ; j++){
					if(map[i][j] == 1){
						count++;
						game(count, w, h, map,i,j);
					}
				}
			}
			System.out.println(count-1);
		}

	}

島の数を数えて、カウントしていきます。

	public static void game (int count, int w, int h, int[][] map, int i, int j){
		
		if(j > 0){
			if(map[i][j-1] == 1){//west
				map[i][j-1] = count;
				game(count, w, h, map,i,j-1);
			}
		}
		if(i > 0){
			if(map[i-1][j] == 1){	//north
				map[i-1][j] = count;
				game(count, w, h, map,i-1,j);
			}
		}
		if(j > 0 && i > 0){
			if(map[i-1][j-1] == 1){	//north-west
				map[i-1][j-1] = count;
				game(count, w, h, map,i-1,j-1);
			}
		}
		if(j < w-1 && i > 0){
			if(map[i-1][j+1] == 1){	//north-east
				map[i-1][j+1] = count;
				game(count, w, h, map,i-1,j+1);
			}
		}
		if(j < w-1){
			if(map[i][j+1] == 1){	//east
				map[i][j+1] = count;
				game(count, w, h, map,i,j+1);
			}
		}
		if(j < w-1 && i < h-1){	
			if(map[i+1][j+1] == 1){	//south-east
				map[i][j+1] = count;
				game(count, w, h, map,i,j+1);
			}
		}
		if(i < h-1){
			if(map[i+1][j] == 1){	//south
				map[i+1][j] = count;
				game(count, w, h, map,i+1,j);
			}
		}
		if(j > 0 && i < h-1){
			if(map[i+1][j-1] == 1){ //south-west
				map[i+1][j-1] = count;
				game(count, w, h, map,i+1,j-1);
			}
		}
	}
}

島の大きさの分だけ再帰して、マップを書き換えます。