TopCoder SRM 577 Div1 Medium EllysChessboard
問題
8x8のグリッドがある。はじめは全て白。指定されたマスを黒に塗りたい。
マスを黒く塗るためのコストは、最初は0.
二個目からは、今まで塗ったマスの中で一番マンハッタン距離が遠いマスとの距離がコスト。
全ての指定されたマスを黒に塗るためのコストの最小値を求めよ。
方針
座標系を45度回転させる。(x, y) -> (x + y, x - y)
すると、変換後の座標(x1, y1), (x2, y2)でのマンハッタン距離は、max(|x1-x2|, |y1-y2|)になる。
これを使えば、今までに塗ったマスのうちx座標, y座標が最小、最大のものをそれぞれ記録しておけば、
新しく塗るためのコストが一意に決められる。
なので、メモ化再帰すればよい。
ソースコード
class EllysChessboard { public: vi x, y; int dp[16][16][16][16]; int rec(int mx, int my, int MX, int MY){ int &res = dp[mx][my + 7][MX][MY + 7]; if(res >= 0) return res; res = inf; rep(i, x.size()) if(!(mx <= x[i] && x[i] <= MX && my <= y[i] && y[i] <= MY)){//新しく塗るもの int nmx = min(mx, x[i]), nmy = min(my, y[i]); int NMX = max(MX, x[i]), NMY = max(MY, y[i]); int sum = max( max(abs(mx - x[i]), abs(MX - x[i])), max(abs(my - y[i]), abs(MY - y[i]))); rep(j, x.size()) if(i != j //新しく塗るものの内部に入ってるやつ && !(mx <= x[j] && x[j] <= MX && my <= y[j] && y[j] <= MY) && (nmx <= x[j] && x[j] <= NMX && nmy <= y[j] && y[j] <= NMY)){ sum += max( max(abs(nmx - x[j]), abs(NMX - x[j])), max(abs(nmy - y[j]), abs(NMY - y[j]))); } res = min(res, sum + rec(nmx, nmy, NMX, NMY)); } if(res == inf) res = 0; return res; } int minCost(vector <string> board) { memset(dp, -1, sizeof(dp)); x.clear(); y.clear(); int ans = inf; rep(i, 8) rep(j, 8) if(board[i][j] == '#') x.pb(i + j), y.pb(i - j); rep(i, x.size()) ans = min(ans, rec(x[i], y[i], x[i], y[i])); return ans == inf ? 0 : ans; } };