本日は午前10：10からTopCoderのSRM587 DIV2。
今回初めて時間内にHARD問題が解けたので、記念メモ。
【Hard 1000 問題文】
H行×W列の格子があります（格子点の数は(H+1)×(W+1)個）。
各格子には”N”か”Z”の文字が与えられ、
”N”であれば格子の左上と右下の点を結び、
”Z”であれば格子の右上と左下の点を結びます。
赤、緑、青の3色を使い、格子点に色を付けていくとき、
隣接する格子点同士で色が異なるように着色可能かどうかを調べ、
可能であれば”Yes”、なければ”No”を返して下さい。
【考察】
日本語で要約すると上記のような感じです。
（正確な問題文や、図による例は、実際の問題文をご参照下さい。）
なんとなく図を描いていると、2×2の格子に注目すればいいことがわかりました。
2×2の格子内で、NとZの数が1：3もしくは3：1であるとき、塗り分けることができません。
（そうでないとき、塗り分けることが可能です。）
すなわち、与えられた格子に含まれる全ての2×2の格子について、
NとZの数を数えることで、着色可能か否かを評価することができます。
本番では次のようなコードを書いたら無事System Testも通過し、696点貰えました。
嬉しかったです。
public class ThreeColorabilityEasy {
public String isColorable(String[] cells) {
int width = cells[0].length();
int height = cells.length;
char[] c = new char[4];
char[][] bad = {{''N'', ''N'', ''N'', ''Z''}, {''N'', ''N'', ''Z'', ''N''}, {''N'', ''Z'', ''N'', ''N''}, {''Z'', ''N'', ''N'', ''N''},
{''Z'', ''Z'', ''Z'', ''N''}, {''Z'', ''Z'', ''N'', ''Z''}, {''Z'', ''N'', ''Z'', ''Z''}, {''N'', ''Z'', ''Z'', ''Z''}};
for(int i = 0; i < width-1; i++){
for(int j = 0; j < height-1; j++){
c[0] = cells[j].charAt(i);
c[1] = cells[j].charAt(i+1);
c[2] = cells[j+1].charAt(i);
c[3] = cells[j+1].charAt(i+1);
for(int k = 0; k < 8; k++){
if(c[0] == bad[k][0] && c[1] == bad[k][1] && c[2] == bad[k][2] && c[3] == bad[k][3]){
return "No";
}
}
}
}
return "Yes";
}
}
今回bad[][]という文字定数の配列を用意して、着色不可能な全てのパターンを入れて、
と冗長気味なコードを書きましたが、他の方々のコードでNもしくはZの数をカウントすればいいことに気付かされました。
それを踏まえて書き直したコードは次のとおり。大分スッキリしました。
public class ThreeColorabilityEasy {
public String isColorable(String[] cells) {
int width = cells[0].length();
int height = cells.length;
int count;
for(int i = 0; i < width-1; i++){
for(int j = 0; j < height-1; j++){
count = 0;
if(cells[j].charAt(i) == ''N'') count++;
if(cells[j].charAt(i+1) == ''N'') count++;
if(cells[j+1].charAt(i) == ''N'') count++;
if(cells[j+1].charAt(i+1) == ''N'') count++;
if(count == 1 || count == 3) return "No";
}
}
return "Yes";
}
}
