定向机器人题解

Dhx20120202

83人浏览 · 2026-08-18 12:11:05

Dhx20120202 · 2026-08-18 12:11:05 发布

定向机器人题解

题意简述

给定一张 $\times m$ 的地图，每个格子有一个方向指示符（U / D / L / R，即上/下/左/右）和一个整数权值 $G_{i,j}$ 。

有一个机器人，可以选择从任意格子出发，但必须用左脚踏入起点。此后，它按照当前所在格子的方向指示符移动（每次只能走到指定的相邻格子，不能斜走），且左右脚必须交替：

左脚踏入某个格子时，获得 $G_{i,j}$ 分；
右脚踏入某个格子时，获得 $G_{i,j}$ 分（即扣除该格子的权值）。

此外，还有一个关键规则：当机器人踏入一个格子并计算得分后，该格子的权值会立即取反（ $G_{i,j} \gets -G_{i,j}$ ）。

机器人可以随时停止 $/$ 移动到地图外结束比赛，获得当前累计得分。

现在，请你对每个格子作为起点，求出从该起点出发（左脚踏入）能获得的最大得分。最后将所有起点的最大得分按给定的哈希方式加权求和输出。

输入格式

第一行包含两个整数 $n, m$ ，表示地图大小。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示地图中每个格子的方向指示符。

接下来 $n$ 行，每行包含 $m$ 个整数，表示地图中每个格子的权值 $G_{i,j}$ 。

输出格式

设 cnt[i][j] 表示以格子 $(i, j)$ 为起点时的最大得分。

你需要按照以下方式计算并输出最终答案 ans：

const long long MOD = 1e9 + 7;
long long ans = 0, base = 1;
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        ans = (ans + cnt[i][j] * base % MOD) % MOD;
        base = base * 131 % MOD;
    }
}
cout << ans << "\n";

简单来说，就是将每个格子的最大得分乘以一个随位置变化的基数 $131^{((i-1)m + (j-1))}$ ，累加后对 $10^9+7$ 取模输出。

数据范围

对于 $10\%$ 的数据： $\le n \le 10$ 。
对于 $40\%$ 的数据： $\le n \le 100$ 。
对于另外 $10\%$ 的数据： $\le n \le 1000$ ，且指示符只可能是 D 或 R。
对于 $100\%$ 的数据： $\le n \le 1000$ ， $-10^9 \le G_{i,j} \le 10^9$ 。

保证指示符只可能是 U、D、L、R 中的一个大写字母。

样例输入 1

3 3
DRD
RUD
DLD
1 2 3
4 5 6
7 8 -1

样例输出 1

-697283612

样例解释 1

每个起点出发的最大得分矩阵为：

3  6  3
5  6  7
7  8 -1

样例输入 2

3 3
RRR
RRD
ULL
1 2 3
4 5 6
7 8 9

样例输出 2

583610153

样例解释 2

每个起点出发的最大得分矩阵为：

2  2  3
5  8  6
11 8  9

提示：样例中的得分矩阵仅供参考，你可以用它来验证自己的计算是否正确。最终输出的是按照哈希方式加权求和后的结果，而不是直接输出矩阵本身。

赛时想法

由于这题是T4，没多想，DFS打个暴力走了。后续也认为这是一道搜索。

正解

1. 图论建模

每个格子有且仅有一个出口（指向上下左右之一），因此整张地图构成一个基环内向树森林：由若干条“链”和若干个“环”组成，每个连通分量恰好有一个环，其余节点通过有向边最终汇入环或走出地图。

出界节点视为终点，不参与环。
每个节点的后继唯一，因此可以用 nxt[u] 存储下一个格子的编号（出界则为 -1）。

2. 链上的 DP

对于不在环上的节点，它们形成有向链，末端要么指向环，要么出界。我们可以从环（或出界点）开始，沿着反向边逆推。

定义状态：

dp[u][0]：从节点 u 出发，当前脚为左脚时的最大得分。
dp[u][1]：从节点 u 出发，当前脚为右脚时的最大得分。

设 to = nxt[u]，转移方程：

dp[u][0] = val[u] + max(0, dp[to][1])
dp[u][1] = -val[u] + max(0, dp[to][0])

其中 max(0, ...) 表示可以在到达 to 后立即停止，不再继续走。

若 to == -1（出界），则：

dp[u][0] = val[u]
dp[u][1] = -val[u]

处理顺序：用三色法（0-未访问，1-在栈中，2-已处理）在线找环。一旦发现环，先调用环的求解函数，再处理指向该环的链，因为链的 DP 依赖环上节点的 dp 值已就绪。

3. 环上的 DP（核心难点）

设环上有 L 个节点，按行走顺序记为 cycle[0..L-1]，权值为 w[0..L-1]。

机器人绕环行走时，每走一圈，所有格子的权值都会取反一次，因此第二圈的权值与第一圈相反。另外，由于左右脚交替的行走方式，所以从不同起点出发时，脚的奇偶模式会偏移。

关键观察：

从环上第 i 个节点出发，若当前脚为 foot（0=左脚，1=右脚），则第 t 步（从0开始）的得分可统一表示为：
$\text{score}(t) = (-1)^{t} \times \text{脚翻转因子} \times \text{权值}$
其中第二圈的权值要额外取反。

在正式推导最优值之前，我们先要知道：以环上的点作为起点时，得分可以为 $0$ 。
比如:

3 3
RRR
RRD
ULL
1 2 3
4 5 6
7 8 9

观察第三行和第四行组成了一个环，现模拟起点为( $2, 1$ )使它的前一个点( $3, 1$ )收益为 $0$ 的情况举例：

第一圈：

从起点( $2, 1$ )出发，积分 $+ 4$ ，当前总积分为 $0 + 4 = 4$ ，( $2, 1$ )分数变为 $- 4$ ，下一步右脚向右；

右脚迈进( $2, 2$ )，积分 $- 5$ ，当前总积分为 $4 - 5 = - 1$ ，( $2, 2$ )分数变为 $- 5$ ，下一步左脚向右；

左脚迈进( $2, 3$ )，积分 $+ 6$ ，当前总积分为 $- 1 + 6 = 5$ ，( $2, 3$ )分数变为 $- 6$ ，下一步右脚向下；

右脚迈进( $3, 3$ )，积分 $- 9$ ，当前总积分为 $5 - 9 = - 4$ ，( $3, 3$ )分数变为 $- 9$ ，下一步左脚向左；

左脚迈进( $3, 2$ )，积分 $+ 8$ ，当前总积分为 $- 4 + 8 = 4$ ，( $3, 2$ )分数变为 $- 8$ ，下一步右脚向左；

右脚迈进( $3, 1$ )，积分 $- 7$ ，当前总积分为 $4 - 7 = - 3$ ，( $3, 1$ )分数变为 $- 7$ ，下一步左脚向上；

左脚迈进( $2, 1$ )，积分 $+ (- 4)$ ，当前总积分为 $- 3 + (- 4) = - 7$ ，( $2, 1$ )分数变为 $4$ ，下一步右脚向右；

第二圈：

右脚迈进( $2, 2$ )，积分 $- (- 5)$ ，当前总积分为 $- 7 - (- 5) = - 2$ ，( $2, 2$ )分数变为 $5$ ，下一步左脚向右；

左脚迈进( $2, 3$ )，积分 $+ (- 6)$ ，当前总积分为 $- 2 + (- 6) = - 8$ ，( $2, 3$ )分数变为 $6$ ，下一步右脚向下；

右脚迈进( $3, 3$ )，积分 $- (- 9)$ ，当前总积分为 $- 8 - (- 9) = 1$ ，( $3, 3$ )分数变为 $9$ ，下一步左脚向左；

左脚迈进( $3, 2$ )，积分 $+ (- 8)$ ，当前总积分为 $1 + (- 8) = - 7$ ，( $3, 2$ )分数变为 $8$ ，下一步右脚向左；

右脚迈进( $3, 1$ )，积分 $- (- 7)$ ，当前总积分为 $- 7 - (- 7) = 0$ ，( $3, 1$ )分数变为 $7$ ，总积分归 $0$ ，结束.

由于网格图是二分图¹，所以环长必定为偶数上，且各个点的地位相同，由此可以使环上任意一个点的收益
至少为 $0$ 。

通过刚才的推演不难发现，以环上的点作为起点时一旦走满两圈，整个环和左右脚交替顺序就会还原至第一步前的初始状态。因此为了高效计算所有起点的最优值，我们采用展开两圈 + 单调队列的方法：

构造基础得分序列
固定从 cycle[0] 出发，用指定脚 foot 走两圈，得到序列 seq[0..2L-1]：
```
seq[i] = (i%2 == foot ? w[i%L] : -w[i%L])   (i < L)
seq[i] = (i%2 == foot ? -w[i%L] : w[i%L])   (i >= L)
```
即第一圈按 foot 确定符号，第二圈整体取反。
前缀和与单调队列
计算 seq 的前缀和 sum[0]=0, sum[i+1]=sum[i]+seq[i]。
对于任意起点 s（ $0 \leq s < L$ ），从 s 出发走不超过 L 步能获得的最大得分等于：
$\max_{e \in [s, s+L-1]} (sum[e+1] - sum[s])$
由于序列已展开两圈，s 对应的真实起点是 cycle[s]。

我们可以枚举终点 e（ $0 \leq e < 2 L$ ），用单调队列维护窗口 [e-L+1, e] 内前缀和最小的起点 s，则当前终点 e 对起点 s 的贡献为 sum[e+1] - sum[s]。遍历所有 e 后，每个起点 s 都取到了所有可能终点的最大值。
符号修正（翻转因子）
sum[e+1] - sum[s] 是基于 seq 序列计算的值，而 seq 本身是基于 cycle[0] 出发的脚态。对于实际起点 cycle[s]，其脚态可能因 s 的奇偶性而与基础脚态 foot 相反。
因此，真正的脚态应为：
```
actual_foot = (s % 2 == 0) ? foot : (1 - foot)
```
将计算结果存入 dp[cycle[s]][actual_foot]。
反向序列补全
仅按正向 cycle 顺序计算会遗漏某些起点的符号组合（因为环的遍历方向固定，但起点偏移会改变奇偶模式）。为此，我们将 seq 反转后再次调用 ring_max，并映射到环上的反向节点 cycle[(L - s) % L]，这样就能覆盖所有情况。
允许得分为0

最后对环上每个节点的 dp[0] 和 dp[1] 取 max(0)，因为机器人可以在环上移动两圈回到起点的前一个点使其分数归 $0$ 。

4. 整体流程

建图，初始化 dp 为极小值。
三色法遍历所有节点：
- 发现环 → 调用 solve_cycle 计算环上节点 → 再调用 solve_chain 处理指向该环的链。
- 遇到已处理节点或出界 → 调用 solve_chain 处理当前路径。
所有节点计算完毕后，用 dp[id][0]（左脚出发）按哈希公式累加输出。

易错点与调试心得

① 第二圈权值取反

在构造两圈序列时，第二圈的权值必须取反，否则环上答案会整体偏高或偏低。这是最隐蔽的 bug 之一，必须在代码中显式判断 i >= L 时取负。

② 脚态映射（`actual_foot`）

actual_foot = (i % 2 == 0) ? foot : 1 - foot 这一行至关重要。很多同学容易忽略，直接用 foot 更新所有节点，导致奇数索引节点的脚态错误，样例中部分点正确、部分点错误就是典型表现。

③ 链的递推顺序

必须在环计算完成后再处理链，因为链末端指向环，依赖环的 dp 值。若顺序颠倒，链会使用未初始化的环值，导致错误。在 find_cc 中，发现环后先 solve_cycle(cycle) 再 solve_chain() 即可。

④ 出界节点的特殊处理

当 nxt[u] == -1 时，dp[u][0] = val[u]，dp[u][1] = -val[u]，不能套用转移公式（否则会访问 dp[-1]）。需在 solve_chain 中判断 to == -1。

⑤ dp 初始化

dp 必须初始化为一个非常小的负数（如 LLONG_MIN），防止未赋值的节点被错误使用。环上至少走一步，链上由末端递推，所有节点最终都会被覆盖。

⑥ 调试技巧

在 solve_cycle 后，用 cout 打印每个环上节点的 dp[0] 和 dp[1]，与手动计算对比。
对整张图，打印所有节点的 dp[0] 矩阵，与题目给的样例解释对照，可以快速定位哪个区域出错。
注意 ring_max 中 tmp 数组的索引映射：tmp[i] 对应起点 i，在 reverse 后映射到 cycle[(L - i) % L]，不要搞反方向。

⑦ 空间与时间

最大点数 $10^6$ ，边数组开 $10^6$ 级别，sum 数组需开到 2*maxn 约 $2\times 10^6$ ，注意内存限制 $512 M B$ ，完全足够。
单调队列用 deque 或手写数组均可，时间复杂度严格 $O (nm)$ ，可过所有数据。

参考代码

下方代码为 AC 实现，关键部分已添加注释，供参考。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int o=1e3+22;

int n,m;

// 方向增量：D(0), U(1), R(2), L(3)
int px[4]={1,-1,0,0};
int py[4]={0,0,1,-1};

struct node
{
    int d;   // 方向编号
    int val; // 权值
};
node a[o][o];

unordered_map<char,int> st; // 方向字符到编号的映射

int nxt[o*o];    // 后继节点编号，-1 表示出界
int val[o*o]={0}; // 节点权值
int dp[o*o][2];  // dp[u][0/1] 表示从 u 出发当前脚为左/右时的最大得分
int tmp[o*o];    // ring_max 临时结果，tmp[i] 表示从环上第 i 个节点出发的最大收益
int sum[o*o*2];  // 前缀和数组（两圈长度）
deque<int> dq;   // 单调队列

vector<int> state(o*o,0); // 0=未访问，1=在栈中，2=已处理
vector<int> path;         // 当前遍历路径

/* ---------- 链的 DP ---------- */
void solve_chain()
{
    if(path.empty()) return;
    for(int i=(int)path.size()-1;i>=0;i--)
    {
        int u=path[i];
        int to=nxt[u];
        if(to==-1) // 出界
        {
            dp[u][0]=val[u];
            dp[u][1]=-val[u];
        }
        else
        {
            // 可随时停止，所以取 max(0, 后续收益)
            dp[u][0]=val[u]+max(0LL, dp[to][1]);
            dp[u][1]=-val[u]+max(0LL, dp[to][0]);
        }
        state[u]=2;
    }
    path.clear();
}

/* ---------- 环的核心计算（单调队列） ---------- */
// w 是长度为 len 的序列，表示从环起点（第0个节点）出发的一圈得分序列
void ring_max(vector<int>& w)
{
    int len=w.size();
    sum[0]=0;
    // 展开两圈，构造前缀和（sum[i] 表示前 i 个元素的和，i 从 1 到 2*len-1）
    for(int i=0;i<2*len;i++)
        sum[i+1]=sum[i]+w[i%len];

    dq.clear();
    for(int i=0;i<2*len;i++)
    {
        // 维护单调递减队列（队首前缀和最大）
        while(!dq.empty() && sum[dq.back()] < sum[i])
            dq.pop_back();
        dq.push_back(i);

        // 移除超出窗口的起点（步数不能超过 len）
        if(i - dq.front() >= len)
            dq.pop_front();

        // 当 i >= len 时，可以确定起点 i-len 的最优值
        if(i >= len)
            tmp[i-len] = sum[dq.front()] - sum[i-len];
    }
}

/* ---------- 环的 DP ---------- */
void solve_cycle(vector<int> &cycle)
{
    int len=cycle.size();
    vector<int> w(len); // 环上权值
    for(int i=0;i<len;i++)
        w[i]=val[cycle[i]];

    for(int ft=0;ft<=1;ft++) // ft=0 左脚，ft=1 右脚
    {
        // 构造从 cycle[0] 出发，脚态为 ft 的一圈得分序列
        vector<int> seq(len,0);
        for(int i=0;i<len;i++)
        {
            if(i%2==ft) seq[i]=w[i];
            else seq[i]=-w[i];
        }

        // 正向计算
        ring_max(seq);
        for(int i=0;i<len;i++)
        {
            int node=cycle[i];
            int actual_foot = (i%2==0) ? ft : 1-ft; // 起点偏移导致脚态翻转
            dp[node][actual_foot] = max(dp[node][actual_foot], tmp[i]);
        }

        // 反转序列，补全所有起点偏移情况
        reverse(seq.begin(), seq.end());
        ring_max(seq);
        for(int i=0;i<len;i++)
        {
            int node=cycle[(len-i)%len]; // 反转后映射回原节点
            int actual_foot = (i%2==0) ? ft : 1-ft;
            dp[node][actual_foot] = max(dp[node][actual_foot], tmp[i]);
        }
    }

    // 允许总分为0
    for(int i=0;i<len;i++)
    {
        dp[cycle[i]][0]=max(dp[cycle[i]][0], 0LL);
        dp[cycle[i]][1]=max(dp[cycle[i]][1], 0LL);
    }
}

/* ---------- 三色法找环与链 ---------- */
void solve_cc()
{
    for(int s=1;s<=n*m;s++)
    {
        if(state[s]!=0) continue;
        int u=s;
        while(1)
        {
            if(state[u]==1) // 发现环
            {
                vector<int> cycle;
                while(!path.empty() && path.back()!=u)
                {
                    cycle.push_back(path.back());
                    path.pop_back();
                }
                cycle.push_back(u);
                path.pop_back(); // 移除 u，path 中剩链

                reverse(cycle.begin(), cycle.end());
                solve_cycle(cycle); // 先算环
                solve_chain();      // 再算链

                for(int v:cycle) state[v]=2;
                break;
            }

            if(state[u]==2 || nxt[u]==-1) // 遇到已处理或出界
            {
                if(nxt[u]==-1) path.push_back(u); // 将出界点加入路径
                solve_chain();
                break;
            }

            // 未访问，继续深入
            state[u]=1;
            path.push_back(u);
            u=nxt[u];
        }
    }
}

/* ---------- 输出答案 ---------- */
void get_ans()
{
    const long long MOD = 1e9 + 7;
    long long ans = 0, base = 1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int id=(i-1)*m+j;
            ans = (ans + dp[id][0] * base % MOD) % MOD;
            base = base * 131 % MOD;
        }
    cout << ans << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 初始化 dp 为极小值
    for(int i=0;i<o*o;i++)
    {
        dp[i][0]=LLONG_MIN;
        dp[i][1]=LLONG_MIN;
    }

    cin>>n>>m;
    st['U']=1; st['D']=0; st['L']=3; st['R']=2;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            a[i][j].d=st[c];
        }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j].val;

    // 建图
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int u=(i-1)*m+j;
            int nx=i+px[a[i][j].d];
            int ny=j+py[a[i][j].d];
            if(nx>=1 && nx<=n && ny>=1 && ny<=m)
                nxt[u]=(nx-1)*m+ny;
            else
                nxt[u]=-1;
            val[u]=a[i][j].val;
        }

    solve_cc();
    get_ans();

    return 0;
}

回顾与总结

这道题是一道很好的基环树+环上DP+单调队列优化的图论题，代码量较大导致我面对了前所未有的挑战。这道题我兜兜转转调了一个多月。过程中也想过放弃。但在不懈努力和优化后终于过了。题目建模的重组、正负性的讨论、单调队列的优化以及最优解的分析都是这题的亮点。我最后也希望训练自己完成更多这样的好题。🎃

以上便是本题的完整题解，包含题意简述、正解推导、易错总结以及带注释的参考代码。希望对大家有所帮助。