/* ACMプログラミングコンテスト 2011 国内予選 【 Problem C 同色パネル結合 】 ■ 問題 以下のように数字の書かれたパネルが四角形の形をしている。左上のパネルの数字を変更して、最終的に指定された数字の島が最大になる場合のその最大値を求める. +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ |1|6|3|2|5| |6|6|3|2|5| |3|3|3|2|5| +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ |2|5|4|6|1| 左上の1を6に変更 |2|5|4|6|1| 左上の6を3に変更 |2|5|4|6|1| (この時点で3の島の最大値は3) +-+-+-+-+-+ +-+-+-+-+-+ (横の6も3になる) +-+-+-+-+-+ |1|2|4|1|5| |1|2|4|1|5| |1|2|4|1|5| +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ 島の定義:パネルが辺で接続している(上下左右のみで斜めは不可) 数字が変更できるパネル:左上のパネルのみ 数字変更のルール:左上のパネルを含む島のすべてのパネルの数字が変更される 色変更の回数:5回 ■ 解答例 色の変更の組み合わせは、6色の順列となる。この順列のすべてについて、指定した色の島の大きさを求めればよい。但し以下の場合には、探索を途中でやめることができる。 探索を途中でやめた場合には、島の大きさが最大になることは無い。 1. 左上のパネルの色と同じ色に変えようとしている。 2. 色を変えても島の大きさが変化しない。 但し、最後の色変更(5回目の色変更)のときは、途中でやめることをしないこととする。 この問題は、とにかく、どの数字であってもよいので、島を大きくしていくことが回答になる。左上のパネルを含む島は、必ず他のパネルと接続しているため、 すべてのパネルの色が同じ色になっている場合を除き、必ず、島を大きくする色の変更があり得る。島の大きさが1つでも大きくなれば、最後に、島のパネル数を 数える色で色変更をすれば、より大きな島を作ることができる。島が大きくならなければ、その色で色を変更したことは無駄なことになってしまうため、 その無駄を含む色変更の組み合わせは、答えにはならない。 但し、指定した色に関しては、最後の色変更時に、その色の最大の島がある場合と、島のパネル数は大きくならないが、その色で島の色を変更した場合に その島が最大パネルの島になる場合がある。そのため、最後の色変更のときのみ、上記の2つのどちらかに適用されても探索を終了しないこととする。 */ import java.io.*; import java.util.*; import java.lang.reflect.*; public class Exp2011_C { /** 配列を桁として扱い、data配列の値を1つ増やす。配列の中の数字で使用できる数字の範囲は、引数のmin以上、max以下とする。 * 例えば、 1,2,5,6,6 という数字がdata配列にあり、min=1、max=6としてこのメソッドを呼ぶと、1,2,6,1,1 となる。 * 右2つの値は桁上げされて最小値の1になり、真ん中の5が6になる。 */ private static boolean increment(int[] data,int min,int max){ for(int cnt=0;cntmax){ data[cnt] = min; }else{ return true; } } return false; } /** * 同じ色で隣り合うパネルを島として認識し、その島の色を変更するメソッド * このメソッドは、2種類の使い方をする。1つは、左上のパネルの色を変える、という処理をするとき。 * もう1つは、問題文で指定された色で構成される島の最大の大きさの島を捜すとき、である。 * この2つの処理においてそれぞれ必要な情報は、引数のparamsに入れられる。 */ private static void island(int[][] panels,int hcnt,int wcnt,int from_color,int to_color,HashMap params){ if(panels[hcnt][wcnt]==from_color){ panels[hcnt][wcnt] = 0; int[] size = (int[])params.get("size"); if(size != null){ size[0]++; } }else{ if(panels[hcnt][wcnt]==to_color){ int[] border = (int[])params.get("border"); if(border!=null){ border[0]++; } } return; } int[][] to_move = {{1,0},{-1,0},{0,1},{0,-1}}; for(int cnt=0;cnt=0 && y=0 && x params = new HashMap(); params.put("size",new int[1]); island(panels,hcnt,wcnt,color,0,params); int size = ((int[])params.get("size"))[0]; if(size > max_space){ max_space = size; } } } } return max_space; } public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new FileReader(args[0])); while(true){ String[] parts = br.readLine().split(" "); int h = Integer.parseInt(parts[0]); int w = Integer.parseInt(parts[1]); int c = Integer.parseInt(parts[2]); if(h == 0){ break; } int[][] start_panels = new int[h][w]; for(int hcnt=0;hcnt params = new HashMap(); params.put("border",new int[1]); island(panels,0,0,panels[0][0],colors[cnt],params); for(int hcnt=0;hcnt max_space){ max_space = space; } } } System.out.print((max_space==-1?h*w:max_space)+"\n"); } } private static void debug_print(int[][] panels){ for(int hcnt=0;hcnt