P5806 题解
CF 上也有一样的题：https://codeforces.com/gym/102392/problem/K。
要不是一个晚上都在肝这道题还没调出来 WC 也不至于打铁 /fn。
假设
这道题最复杂的地方就在于处理输入，其实只要精细实现就可以规避很多问题。
首先，由于机器人只能在有光照的地方，所以真正有意义的点（定义其为「关键点」）最多只有
- 某个方向上没有障碍；
- 这个点没有障碍；
- 在对应反方向上恰好一单位处有障碍。
下一步要对这些点编号，但由于一个点可能会被多个方向上的光照到，所以要进行去重。（可以 Hash，也可以记录某个点是否存在然后从已经记录过的方向上找）
然后是连边。1、2 两类边是平凡的，第三类则可以对于一个点和一个方向，枚举这个方向上在这个点上方的其他点并连边。易证这样的枚举量不会超过
由于边权都是
然后，就码吧。注意精细实现，常数不是很紧。（我写的还是太丑了）
#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;
}