自动搬运

查看原文

来自洛谷，原作者为

	5ab_juruo May you find some comfort here

搬运于2025-08-24 22:14:32，当前版本为作者最后更新于2022-01-27 20:28:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

CF 上也有一样的题：https://codeforces.com/gym/102392/problem/K。

要不是一个晚上都在肝这道题还没调出来 WC 也不至于打铁 /fn。

假设 $n$，$m$，$l$ 同阶。

这道题最复杂的地方就在于处理输入，其实只要精细实现就可以规避很多问题。

首先，由于机器人只能在有光照的地方，所以真正有意义的点（定义其为「关键点」）最多只有 $6n^2$ 个。注意这些点要满足：

• 某个方向上没有障碍；
• 这个点没有障碍；
• 在对应反方向上恰好一单位处有障碍。

下一步要对这些点编号，但由于一个点可能会被多个方向上的光照到，所以要进行去重。（可以 Hash，也可以记录某个点是否存在然后从已经记录过的方向上找）

然后是连边。1、2 两类边是平凡的，第三类则可以对于一个点和一个方向，枚举这个方向上在这个点上方的其他点并连边。易证这样的枚举量不会超过 $3n^3$。

由于边权都是 $1$，最后跑一个 bfs 就好了，复杂度 $O(n^3)$。

然后，就码吧。注意精细实现，常数不是很紧。（我写的还是太丑了）

#include <queue>
#include <cstdio>
#include <bitset>
#include <cstring>
using namespace std;

typedef long long ll;
const int max_n = 500, efct = 36, nfct = 6, max_sn = max_n * max_n;
typedef int (*A)[max_n];

#define S [max_n][max_n]
#define C(x, v) memset(x, v, sizeof x)

char tmp[max_n][max_n][max_n+1];
bitset<max_sn> ex[max_n];
int da S, db S, dc S, dd S, de S, df S, pa S, pb S, pc S, pd S, pe S, pf S;
int ind = 0, n, m, l;
int hd[max_sn*nfct], des[max_sn*efct], nxt[max_sn*efct], dis[max_sn*nfct], e_cnt = 0;

inline void add(int s, int t)
{
	des[e_cnt] = t;
	nxt[e_cnt] = hd[s];
	hd[s] = e_cnt++;
}

// 记录编号，为了省常数写了三个
void RA(A da, A pa)
{
	for (int i = 0, j, k = 0; i < m; i++)
		for (j = 0; j < l; j++, k++)
			if (da[i][j] != -1)
				pa[i][j] = ind++, ex[da[i][j]][k] = true;
}

void RB(A dc, A pc)
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < l; j++)
			if (dc[i][j] != -1)
			{
				if (!ex[i][dc[i][j]*l+j])
					pc[i][j] = ind++, ex[i][dc[i][j]*l+j] = true;
				else
					pc[i][j] = (da[dc[i][j]][j] == i)? pa[dc[i][j]][j]:pb[dc[i][j]][j];
			}
}

void RC(A de, A pe)
{
	for (int i = 0, j, k, t, x; i < n; i++)
		for (j = 0, k = 0; j < m; j++, k += l)
			if ((t = de[i][j]) != -1)
			{
				if (!ex[i][k+t])
					pe[i][j] = ind++, ex[i][k+t] = true;
				else
				{
					if (da[j][t] == i)
						pe[i][j] = pa[j][t];
					else if (db[j][t] == i)
						pe[i][j] = pb[j][t];
					else if (dc[i][t] == j)
						pe[i][j] = pc[i][t];
					else
						pe[i][j] = pd[i][t];
				}
			}
}

// 加 1,2 两类边，这里正向和反向一起加
void E(A da, A pa, A db, A pb, int m, int l)
{
	for (int i = 1; i < m; i++)
		for (int j = 0; j < l; j++)
		{
			if (da[i-1][j] != -1 && da[i][j] != -1)
			{
				if (da[i-1][j] <= da[i][j])
					add(pa[i-1][j], pa[i][j]);
				if (da[i-1][j] >= da[i][j])
					add(pa[i][j], pa[i-1][j]);
			}
			if (db[i-1][j] != -1 && db[i][j] != -1)
			{
				if (db[i-1][j] >= db[i][j])
					add(pb[i-1][j], pb[i][j]);
				if (db[i-1][j] <= db[i][j])
					add(pb[i][j], pb[i-1][j]);
			}
		}
	for (int i = 0; i < m; i++)
		for (int j = 1; j < l; j++)
		{
			if (da[i][j-1] != -1 && da[i][j] != -1)
			{
				if (da[i][j-1] <= da[i][j])
					add(pa[i][j-1], pa[i][j]);
				if (da[i][j-1] >= da[i][j])
					add(pa[i][j], pa[i][j-1]);
			}
			if (db[i][j-1] != -1 && db[i][j] != -1)
			{
				if (db[i][j-1] >= db[i][j])
					add(pb[i][j-1], pb[i][j]);
				if (db[i][j-1] <= db[i][j])
					add(pb[i][j], pb[i][j-1]);
			}
		}
}

// 找坐标对应的关键点
int sek(int x, int y, int z)
{
	#define G(d, p, k, i, j)\
	if (d[i][j] == k)\
		return p[i][j];
	G(da, pa, x, y, z) G(db, pb, x, y, z)
	G(dc, pc, y, x, z) G(dd, pd, y, x, z)
	G(de, pe, z, x, y) G(df, pf, z, x, y)
	return -114514;
}

signed main()
{
	int sx, sy, sz, tx, ty, tz;
	
	scanf("%d%d%d", &l, &m, &n);
	C(da, -1), C(db, -1), C(dc, -1), C(dd, -1), C(de, -1), C(df, -1), C(hd, -1);
	
	for (int i = 0, j, k; i < n; i++)
		for (j = 0; j < m; j++)
		{
			scanf("%s", tmp[i][j]);
			for (k = 0; k < l; k++)
			{
				if (tmp[i][j][k] == 'R')
					sx = i, sy = j, sz = k;
				else if (tmp[i][j][k] == 'T')
					tx = i, ty = j, tz = k;
			}
		}
	
    // 找关键点
	for (int i = 0, j, k; i < m; i++)
		for (j = 0; j < l; j++)
		{
			if (tmp[0][i][j] != '*')
				for (k = 1; k < n; k++)
					if (tmp[k][i][j] == '*')
					{
						if (tmp[k-1][i][j] != '*')
							da[i][j] = k - 1;
						break;
					}
			if (tmp[n-1][i][j] != '*')
				for (int k = n - 1; k > 0; k--)
					if (tmp[k-1][i][j] == '*')
					{
						if (tmp[k][i][j] != '*')
							db[i][j] = k;
						break;
					}
		}
	for (int i = 0, j, k; i < n; i++)
		for (j = 0; j < l; j++)
		{
			if (tmp[i][0][j] != '*')
				for (k = 1; k < m; k++)
					if (tmp[i][k][j] == '*')
					{
						if (tmp[i][k-1][j] != '*')
							dc[i][j] = k - 1;
						break;
					}
			if (tmp[i][m-1][j] != '*')
				for (int k = m - 1; k > 0; k--)
					if (tmp[i][k-1][j] == '*')
					{
						if (tmp[i][k][j] != '*')
							dd[i][j] = k;
						break;
					}
		}
	for (int i = 0, j, k; i < n; i++)
		for (j = 0; j < m; j++)
		{
			if (tmp[i][j][0] != '*')
				for (k = 1; k < l; k++)
					if (tmp[i][j][k] == '*')
					{
						if (tmp[i][j][k-1] != '*')
							de[i][j] = k - 1;
						break;
					}
			if (tmp[i][j][l-1] != '*')
				for (int k = l - 1; k > 0; k--)
					if (tmp[i][j][k-1] == '*')
					{
						if (tmp[i][j][k] != '*')
							df[i][j] = k;
						break;
					}
		}
	
	C(pa, -1), C(pb, -1), C(pc, -1), C(pd, -1), C(pe, -1), C(pf, -1);
	RA(da, pa); RA(db, pb);
	RB(dc, pc), RB(dd, pd);
	RC(de, pe), RC(df, pf);
	E(da, pa, db, pb, m, l);
	E(dc, pc, dd, pd, n, l);
	E(de, pe, df, pf, n, m);
	
    // 加第三类边
	#define HA(p, u, v, t)\
	if (da[u][v] == t)\
		add(pa[u][v], p[i][j]);\
	else if (db[u][v] == t)\
		add(pb[u][v], p[i][j]);
	#define HC(p, u, v, t)\
	if (dc[u][v] == t)\
		add(pc[u][v], p[i][j]);\
	else if (dd[u][v] == t)\
		add(pd[u][v], p[i][j]);
	#define HE(p, u, v, t)\
	if (de[u][v] == t)\
		add(pe[u][v], p[i][j]);\
	else if (df[u][v] == t)\
		add(pf[u][v], p[i][j]);
	for (int i = 0, j, k, s = 0; i < m; i++)
		for (j = 0; j < l; j++, s++)
		{
			if (da[i][j] != -1)
				for (k = 0; k < da[i][j]; k++)
					if (ex[k][s]) { HC(pa, k, j, i) HE(pa, k, i, j) }
			if (db[i][j] != -1)
				for (k = db[i][j] + 1; k < n; k++)
					if (ex[k][s]) { HC(pb, k, j, i) HE(pb, k, i, j) }
		}
	for (int i = 0, j, k, s; i < n; i++)
		for (j = 0; j < l; j++)
		{
			if (dc[i][j] != -1)
				for (k = 0, s = 0; k < dc[i][j]; k++, s += l)
					if (ex[i][s+j]) { HA(pc, k, j, i) HE(pc, i, k, j) }
			if (dd[i][j] != -1)
				for (k = dd[i][j] + 1; k < m; k++)
					if (ex[i][k*l+j]) { HA(pd, k, j, i) HE(pd, i, k, j) }
		}
	for (int i = 0, j, k, s; i < n; i++)
		for (j = 0, s = 0; j < m; j++, s += l)
		{
			if (de[i][j] != -1)
				for (k = 0; k < de[i][j]; k++)
					if (ex[i][s+k]) { HA(pe, j, k, i) HC(pe, i, k, j) }
			if (df[i][j] != -1)
				for (k = df[i][j] + 1; k < l; k++)
					if (ex[i][s+k]) { HA(pf, j, k, i) HC(pf, i, k, j) }
		}
	
	queue<int> q;
	C(dis, 0x3f);
	
    // 确认起点和终点是否都在关键点上
	sx = sek(sx, sy, sz), tx = sek(tx, ty, tz);
	if (sx == -114514 || tx == -114514)
	{
		puts("-1");
		return 0;
	}
	q.push(sx), dis[sx] = 0;
	
	int cur;
	while (!q.empty()) // BFS
	{
		cur = q.front(), q.pop();
		for (int p = hd[cur]; p != -1; p = nxt[p])
			if (dis[des[p]] > dis[cur] + 1)
			{
				dis[des[p]] = dis[cur] + 1;
				q.push(des[p]);
			}
	}
	
	if (dis[tx] >= 0x3f3f3f)
		puts("-1");
	else
		printf("%d\n", dis[tx]);
	
	return 0;
}