TIOJ-1099

發表於 更新於 Disqus：

在一個長寬高為$n$的三維空間中，每次在座標$(x, y, z)$可以跳到以下任一個:

  • $(y, x, z)$
  • $(x, z, y)$
  • $(z, x, y)$
  • $(2y - x + 1, 2x - y - 1, z)$

給定起始點$(x_1, y_1, z_1)$，問能不能跳到$(x_2, y_2, z_2)$

$n\le 3000$

直觀下可以直接跑dfs，記錄三維的造訪狀態(走過的不要走)，這樣是$\mathcal{O}(N^3)$。
之後想了好久orz，還是去被暴雷後才知道怎麼做QQ

如何更快?
考慮$x+y+z=k$，前三種方式很顯然的移動後總和仍$=k$，至於第四種:
$$(2y - x + 1) + (2x - y - 1) + z = x + y + z = k$$
所以三個座標的總和為定值，此時狀態只需要紀錄兩個維度就好!!
複雜度$\mathcal{O}(N^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*-----------------------------------------------------------------------------------------------------*/

signed main() {
	EmiliaMyWife

	int n, a, b, c, d, e, f;
	while(cin >> n >> a >> b >> c >> d >> e >> f, n) {
		if(a + b + c != d + e + f) {
			cout << "No\n";
			continue;
		}
		vector<vector<bool>> ok(n + 1, vector<bool>(n + 1));
		const function<void(int, int, int)> dfs = [&] (int x, int y, int z) {
			if(x < 0 || y < 0 || z < 0 || x > n || y > n || z > n)
				return;
			if(ok[x][y])
				return;
			ok[x][y] = 1;
			dfs(y, x, z);
			dfs(x, z, y);
			dfs(z, y, x);
			dfs(2 * y - x + 1, 2 * x - y - 1, z);
		};
		dfs(a, b, c);
		cout << (ok[d][e] ? "Yes" : "No") << '\n';
	}

	return 0;
}