CWOI S C0281 D 棋盤

題意

使用 openssl enc -aes256 -pbkdf2 -a 加密。

U2FsdGVkX187NyPTtVajyNS83bfTBw+nUU2o4e8EMUgKvXl3lwqKBx+mKL4/LWqp
tuz8INyEYPSMAW9pnFaJEDnDbOLE5/eipbg+Zg3LCtGLZTR5f08XRiW5wlyS/ROj
aF7imQPtHAxG7d19V4U2eU/K8mctdqYv4pXa0CYnUn1015MBJlg0XkqQiNBo7STM
r+/vdnIdLT7bS2ipAjdOD09DfeRMqyAWBxX/xhtUBi1mQ+oZ52AZz4ug44znYlMb
ZwTBuMzP1nLuJeLWkzfVxPaerBYCG6EvEBW/SyVLAlTUj7PYjwVssXnlxYn3pDPA
C8+8gZsz9EyyePz6pE5JjQ==

解析

關於 Manhattan 距離，有一個常見的 trick，即如果一個點為 $(x, y)$，則可以轉化為 $(x', y') = (x + y, x - y)$，這樣 $|x_1-x_2|+|y_1-y_2|$ 就可以變為 $\max\{|x'_1-x'_2|, |y'_1-y'_2|\}$。前者為 Manhattan 距離，後者為 Chebyshev 距離。

首先我們先將棋盤上所有點的座標按照上面的方法轉換成可以用 Chebyshev 距離計算的坐標。對於轉換完的點，令 $f(S)$ 表示點集為 $S$ 時最小代價。

我們在 $S$ 中找到 $x$ 最大、最小，$y$ 最大、最小的點，這裡我們分別記作 B、D、A、 C（如果有多個一樣大就隨便找一個）。如果 $x_B - x_D > y_A - y_C$，那麼我們就從 $f(S \setminus B)$ 和 $f(S \setminus D)$ 中轉移；如果 $x_B - x_D < y_A - y_C$，那麼我們就從 $f(S \setminus A)$ 和 $f(S \setminus C)$ 中轉移。如果相等，就隨便。

這樣做是正確的，以 $x_B - x_D > y_A - y_C$ 為例，可以肯定的是 $x_B - x_D$ 這個一定會在某次計算代價時被計算到。而對於 $B$ 和 $D$ 以外的點，如果我們先把 $B$ 或 $D$ 刪除了，刪除他們的代價會變小，總的來說，先刪除 $B$ 或 $D$ 不劣。

同時時間複雜度也是正確的。考慮將 $(x, y)$ 轉換成 $(x + y, x - y)$ 之後，最極限的情況，一條邊上最多有 4 個點，這個刪點的過程，從某個矩形刪成縮小的矩形，狀態數是 $2^4 \times 2^4$，即像對兩條矩形邊上的點數相乘。最多可能的矩形數量是 $16^4$ 級別的。所以總共狀態數上界是 $2^8 \times 16^4$，而且不可能卡滿。

實現

int main()
{
	std::vector<std::pair<int, int>> dot;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			char ch;
			std::cin >> ch;
			if (ch == '#') dot.emplace_back(i + j, i - j);
		}
	}

	std::map<std::vector<std::pair<int, int>>, int> f;

	auto comp_first = [](std::pair<int, int> a, std::pair<int, int> b)
	{
		return a.first < b.first;
	};
	auto comp_second = [](std::pair<int, int> a, std::pair<int, int> b)
	{
		return a.second < b.second;
	};
	
	auto dfs = [&f, comp_first, comp_second](auto &&self, std::vector<std::pair<int, int>> dot) -> int
	{
		if (dot.size() <= 1) return 0;
		if (f.contains(dot)) return f[dot];

		auto min_first = std::min_element(dot.begin(), dot.end(), comp_first);
		auto max_first = std::max_element(dot.begin(), dot.end(), comp_first);
		auto min_second = std::min_element(dot.begin(), dot.end(), comp_second);
		auto max_second = std::max_element(dot.begin(), dot.end(), comp_second);

		auto res = std::numeric_limits<int>::max();

		auto wfirst = max_first->first - min_first->first;
		auto wsecond = max_second->second - min_second->second;
		if (wfirst > wsecond) {
			{
				auto backup = dot;
				dot.erase(min_first);
				res = std::min(res, self(self, dot) + wfirst);
				dot = backup;
			}
			{
				auto backup = dot;
				dot.erase(max_first);
				res = std::min(res, self(self, dot) + wfirst);
				dot = backup;
			}
		} else {
			{
				auto backup = dot;
				dot.erase(min_second);
				res = std::min(res, self(self, dot) + wsecond);
				dot = backup;
			}
			{
				auto backup = dot;
				dot.erase(max_second);
				res = std::min(res, self(self, dot) + wsecond);
				dot = backup;
			}
		}

		f[dot] = res;
		return res;
	};

	std::cout << dfs(dfs, dot) << std::endl;
}