DucksAlignment

2011-12-07

23:34 |

縦か横か、どの列/行に揃えるか決めて、

揃えるコスト＋「ダックを並べ始めるとこからダックの数だけ、想定する場所に動かすためのコストの最小値」を計算する。

その最小値が答え。

説明しづらい。

方針を考えるのが遅い。実装もバグがいくつか。むむむむむ

practice で system test pass

class DucksAlignment {
	public:
	int minimumTime(vector <string> grid) {
		int N=0;
		int H=grid.size();
		int W=grid[0].size();
		VI v0, v1;
		REP(y, H) {
			REP(x, W) {
				if(grid[y][x]=='o') {
					v0.push_back(x);
					v1.push_back(y);
					N++;
				}
			}
		}
		sort(ALL(v0));
		int ans = 100000000;
		REP(ii, 2) {
			int L=ii==0?H:W;
			FOR(ai, v0) {
				int lans = 0;
				FOR(v, v0) {
					lans += abs(*ai-*v);
				}
				int lans2=1000000;
				REP(be, L-N+1) {
					int llans2=0;
					REP(i, N) {
						llans2 += abs(be+i - v1[i]);
					}
					lans2 = min(lans2, llans2);
				}
				ans = min(ans, lans+lans2);
			}
			swap(v0, v1);
		}
		return ans;
	}