TopCoder/SRM498/FoxStones

出展 †

• TopCoder SRM498(Div1 Medium) (問題文)

問題 †

N×Mの各セルにそれぞれ異なる石が置いてあり，うち何個かのセルにはマークがついている．
全ての石について，各マーク付きセルからの距離が元の配置と全て等しくなるような石の並べ方をsimilar layoutという．
ここで，(x1,y1)と(x2,y2)との距離はmax(|x1-x2|, |y1-y2|)により定義する．
与えられたN, M, マーク付きセルの位置について，similar layoutの数を求めなさい．

解法 †

• 各セルについて，各マーク付きセルからの距離の組を計算する．
• このとき，距離の組が同じであるセル間では石の交換が可能．
• なので，距離の組ごとにセルを集合に分けて，各集合の要素数の階乗の積が答え．

回答 †

• FoxStones_pes.cpp - mapによる実装(pes)