[AlgoSpot] BoardCover


問題のショートカット
Github Source

問題の概要



ゲームボードが与えられた場合、「ㄱ」パターンを用いてゲームボードを埋め込む方法数の問題を求める.

に答える

mapでは、壁や「ㄱ」の形をした図形を充填し、順次空白空間を巡回し、その位置に4種類のブロックを代入して計算する.
すなわち、プロセスを例にとると、以下のようになる.
1. 다음 빈 좌표로 이동
2. 'ㄱ'모양 도형 채워넣기 (방향 돌려가면서 반복!!)
    2-1. 다음 빈 좌표로 이동
    2-2. 'ㄱ'모양 도형 채워넣기
        2-2-1. 다음 빈 좌표로 이동
        2-2-2. 'ㄱ'모양 도형 채워넣기
            (계속 깊게 반복하다가 return)
        2-2-3. 'ㄱ'모양 도형 지우기
    2-3. 'ㄱ'모양 도형 지우기
3. 'ㄱ'모양 도형 지우기
前述の例のように、[座標移動](Coordinate Move)、[シェイプの塗りつぶし](Shape Fill)、[再帰](Recursion)、[シェイプの消去](Shape Erase)の処理は、おおよそ行われます.
次のコードに実装します.
private void recursive(Pair coord)
{
	if (isAllFilled())
	{
		Answer++;
		return;
	}

	coord = nextPair(coord);

	for (int blockType = 0; blockType < blocks.length; blockType++)
	{
		if (isFillPossible(coord, blockType))
		{
			fillBlock(coord, blockType);
			recursive(coord);
			deleteBlock(coord, blockType);
		}
	}
}