Google DevFest 2010 Quizのパッチワーク問題
パッチワーク
ここに "A" または "B" という文字のみを含む 600 桁、600 行のテキストがあります。これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。
まず、最も多くの文字がつながっている領域をすべて "_" で塗りつぶしてください。 最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を "_"で塗りつぶすこととします。
そして、各行ごとに "_" が何個含まれているかを数え、それらの数値を改行区切りのテキスト（600 行）として答えてください。
以下の例1を見てください。この入力には単一の文字4つでつながった領域が3箇所あります。これらすべてが「最も多くの文字がつながっている領域」なので、全て"_"で塗りつぶし、その数を数えています。
いろいろ回答例が晒されてるので、自分のも晒してみます。ベタベタですが。
やってることは、ファイルの内容をPatchクラスの二次元配列に変換して、最大領域を占める部分の検出、および指定した文字列への変換をして、最後に集計してるってだけです。
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.ArrayList; import java.util.List; /** * パッチワーク問題の回答 * * @author matsukaz */ public class Main { private static final String INPUT_FILE = "patchworkinput.txt"; private static final String OUTPUT_FILE = "patchworkoutput.txt"; private static final int MAX_LINE_SIZE = 600; private static final int MAX_ROW_SIZE = 600; private static final char REPLACE_CHAR = '_'; /** * メイン * * @param args */ public static void main(String[] args) { Patch[][] patches = createPatches(INPUT_FILE, MAX_LINE_SIZE, MAX_ROW_SIZE); List<Patch[]> maxPatchAreaList = getMaxPatchAreaList(patches); replaceVal(maxPatchAreaList); // outputPatches(patches, OUTPUT_FILE); outputPatchesCnt(patches, OUTPUT_FILE); } /** * ファイルを読み込んでPatchクラスの二次元配列に変換する。 * * @param fileName * @param maxLineSize * @param maxRowSize * @return */ private static Patch[][] createPatches(final String fileName, final int maxLineSize, final int maxRowSize) { Patch[][] patches = new Patch[maxLineSize][maxRowSize]; int linePos = 0; BufferedReader reader = null; try { String line = null; reader = new BufferedReader(new FileReader(fileName)); while ((line = reader.readLine()) != null) { int rowSize = line.length(); for (int rowPos = 0;rowPos < rowSize; rowPos++) { patches[linePos][rowPos] = new Patch(linePos, rowPos, line.charAt(rowPos)); } linePos++; } } catch(IOException e) { throw new RuntimeException(e); } finally { try { reader.close(); } catch (IOException e) {} } return patches; } /** * Patchクラスの二次元配列のうち、最大領域を占めるPatchクラスの * 配列のリストを返す。本来であればPatchクラスの配列のみで良いが、 * 最大領域が複数存在する（数が一致する）場合を考えリストにしている。 * * @param patches * @return */ private static List<Patch[]> getMaxPatchAreaList(final Patch[][] patches) { List<Patch[]> maxPatchAreaList = null; int maxPatchAreaCnt = 0; int maxLineSize = patches.length; for (int linePos = 0; linePos < maxLineSize; linePos++) { int maxRowSize = patches[linePos].length; for (int rowPos = 0; rowPos < maxRowSize; rowPos++) { Patch patch = patches[linePos][rowPos]; List<Patch> result = new ArrayList<Patch>(); checkPatchArea(patches, patch, patch.val, result); if (maxPatchAreaCnt < result.size()) { maxPatchAreaCnt = result.size(); maxPatchAreaList = new ArrayList<Patch[]>(); maxPatchAreaList.add( result.toArray(new Patch[result.size()])); } else if (maxPatchAreaCnt == result.size()) { maxPatchAreaList.add( result.toArray(new Patch[result.size()])); } } } return maxPatchAreaList; } /** * 指定された領域が対象か否かチェックする。 * 対象の場合は上下左右の領域を再帰チェックする。 * * @param patches * @param patch * @param val * @param result */ private static void checkPatchArea(final Patch[][] patches, final Patch patch, final char val, final List<Patch> result) { if (patch.isDone) return; // すでにチェック済みの領域はスキップ if (val != patch.val) return; // 値が一致しない場合はスキップ patch.isDone = true; result.add(patch); if (patch.linePos > 0) { // 上のセル確認 checkPatchArea(patches, patches[patch.linePos - 1][patch.rowPos], patch.val, result); } if (patch.rowPos < patches[patch.linePos].length - 1) { // 右のセルを確認 checkPatchArea(patches, patches[patch.linePos][patch.rowPos + 1], patch.val, result); } if (patch.linePos < patches.length - 1) { // 下のセルを確認 checkPatchArea(patches, patches[patch.linePos + 1][patch.rowPos], patch.val, result); } if (patch.rowPos > 0) { // 左のセルを確認 checkPatchArea(patches, patches[patch.linePos][patch.rowPos - 1], patch.val, result); } } /** * 最大領域を占めるPatchクラスの配列のリストの値を指定された文字に置き換える。 * * @param maxPatchAreaList */ private static void replaceVal(List<Patch[]> maxPatchAreaList) { for (Patch[] patches : maxPatchAreaList) { for (Patch patch : patches) { patch.val = REPLACE_CHAR; } } } /** * 文字列を置き換えた状態でファイル出力する。 * * @param patches * @param fileName */ private static void outputPatches(final Patch[][] patches, final String fileName) { String separator = System.getProperty("line.separator"); BufferedWriter writer = null; try { writer = new BufferedWriter(new FileWriter(fileName)); int maxLineSize = patches.length; for (int linePos = 0; linePos < maxLineSize; linePos++) { int maxRowSize = patches[linePos].length; char[] line = new char[maxRowSize]; for (int rowPos = 0; rowPos < maxRowSize; rowPos++) { line[rowPos] = patches[linePos][rowPos].val; } writer.write(line); writer.write(separator); } } catch(IOException e) { e.printStackTrace(); } finally { try { writer.close(); } catch (IOException e) {} } } /** * 置き換えられた文字列をカウントした結果を出力する。 * * @param patches * @param fileName */ private static void outputPatchesCnt(final Patch[][] patches, final String fileName) { String separator = System.getProperty("line.separator"); BufferedWriter writer = null; try { writer = new BufferedWriter(new FileWriter(fileName)); int maxLineSize = patches.length; for (int linePos = 0; linePos < maxLineSize; linePos++) { int targetCnt = 0; int maxRowSize = patches[linePos].length; for (int rowPos = 0; rowPos < maxRowSize; rowPos++) { if (patches[linePos][rowPos].val == REPLACE_CHAR) { targetCnt++; } } writer.write(Integer.toString(targetCnt)); writer.write(separator); } } catch(IOException e) { e.printStackTrace(); } finally { try { writer.close(); } catch (IOException e) {} } } } /** * パッチを表すクラス * * @author matsukaz */ class Patch { public int linePos; public int rowPos; public boolean isDone = false; public char val; public Patch(int linePos, int rowPos, char val) { this.linePos = linePos; this.rowPos = rowPos; this.val = val; } }
