Coalescing Continents (UVa Live Archive Asia - 2011 Phuket)
問題
20*20の盤面に最大5個の長方形の大陸がある。大陸の大きさの合計は25である。大陸を動かして正方形を作りたいが最小何回大陸を移動させないといけないか?
移動させる時は大陸は重なっても良い。
解法
まず5*5の正方形にどう大陸を敷き詰めるかを考える。それが終わったら、5*5の正方形を盤面のどこに置くか考えれば良い。
20*20の盤面に最大5個の長方形の大陸がある。大陸の大きさの合計は25である。大陸を動かして正方形を作りたいが最小何回大陸を移動させないといけないか?
移動させる時は大陸は重なっても良い。
まず5*5の正方形にどう大陸を敷き詰めるかを考える。それが終わったら、5*5の正方形を盤面のどこに置くか考えれば良い。