パッチワーク問題 ( Google Dev Fest ) を解いてみました。

昼寝しすぎて、眠れなかったので


Google Dev Festの パッチワーク問題を解いてみましたｗ
いろいろな回答例が公開されていて、今更ですが

ソースは Java です。「解ければいいでしょ」って感じで、かなり雑なソースです
(久しぶりに、再帰呼出しつかったよｗ)

さーて、もう寝よう

PatchWork.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class PatchWork {
	
	private String board[] ;
	private char[][] temp;
	private int count;
	private int max;
	private List<Integer> pos = new ArrayList<Integer>();
	private int rowCounter[] ;
	
	public static void main(String[] args) {
		new PatchWork().start();
	}

	private void disp() {
		for (int y = 0 ; y < temp.length ; y++) {
			for (int x = 0 ; x < temp[y].length ; x++) {
				System.out.print(temp[y][x]);
			}
			System.out.println();
		}
		System.out.println();
	}
	
	public void start() {
		
		init();

		clear();

		for (int y = 0 ; y < temp.length ; y++) {
			for (int x = 0 ; x < temp[y].length ; x++) {
				if (temp[y][x] != '_') {

					count = 0;
					
					search(y,x,temp[y][x]);
					
					if (count >= max) {
						if (count > max) {
							pos.clear();
						}
						pos.add(x << 16 | y);
						max = count;
					}
					
				}
			}
		}

		clear();
		
		for (int xy : pos) {
			int y = xy & 0xffff;
			int x = xy >> 16;
			search(y,x,temp[y][x]);
		}

		disp();
		
		for (int y = 0 ; y < rowCounter.length ; y++) {
			System.out.println(rowCounter[y]);
		}
		
	}
	
	private void init() {
		InputStream in = Thread.currentThread().getContextClassLoader().getResourceAsStream("input.txt");
		BufferedReader br = new BufferedReader(new InputStreamReader(in));
		
		try {
			String line;
			List<String> lines = new ArrayList<String>();
			while ((line = br.readLine()) != null) {
				lines.add(line);
			}
			
			board = lines.toArray(new String[0]);
			
		} catch (IOException e) {
			throw new RuntimeException("ファイル読み込み失敗",e);
		}
		
	}
	
	private void clear() {
		
		temp = new char[board.length][];
		
		for (int i = 0 ; i < board.length ; i++) {
			temp[i] = board[i].toCharArray();
		}
		rowCounter = new int[temp.length];
	}
	
	private void search(int y,int x,char c) {
		
		count++;

		rowCounter[y]++;
		
		temp[y][x] = '_';

		if (y - 1 >= 0) {
			if (temp[y - 1][x] == c) {
				search(y - 1, x, c);
			}
		}

		if (y + 1 < temp.length) {
			if (temp[y + 1][x] == c) {
				search(y + 1, x, c);
			}
		}
		
		if (x - 1 >= 0) {
			if (temp[y][x - 1] == c) {
				search(y, x - 1, c);
			}
		}

		if (x + 1 < temp[y].length) {
			if (temp[y][x + 1] == c) {
				search(y, x + 1, c);
			}
		}

	}
	
}