eJOI 2019 Problem F. Awesome Arrowland Adventure 题解

题目大意

给定一个 $n \times m$ 的网格，每个格子有一个箭头（N、E、S、W）或障碍物（X）。选手从 $(1,1)$ 出发，按照当前格子的箭头方向移动到相邻格子。每次可以顺时针旋转箭头90度（代价为1次旋转）。求从起点到终点的最小旋转次数，若无法到达输出 -1。

算法思路

核心思想：最短路建模

将问题转化为图论最短路问题：

• 每个网格位置作为一个节点
• 箭头旋转次数作为边权
• 使用 Dijkstra 算法 求最小代价

关键洞察

对于每个箭头格子，可以旋转到4个方向，旋转代价为：

• 0次：保持原方向
• 1次：顺时针转90度
• 2次：转180度
• 3次：转270度

图构建策略

对于每个箭头格子 $(i,j)$ 和它的4个邻居方向 $k$：

• 计算从当前箭头方向转到目标方向 $k$ 的旋转次数
• 添加从 $(i,j)$ 到邻居的边，权值为旋转次数

旋转代价计算

int get(char c) {
    if (c == 'E') return 0;
    if (c == 'S') return 1; 
    if (c == 'W') return 2;
    return 3; // 'N'
}

// 计算旋转代价
d <= k ? k - d : 4 - d + k;

解释：

• d：当前箭头方向编号（0:E, 1:S, 2:W, 3:N）
• k：目标方向编号（0:东, 1:南, 2:西, 3:北）
• 如果 d <= k：直接顺时针旋转 k-d 次
• 否则：先转到E(0)再转到目标方向，代价 4-d+k

算法流程

1. 方向映射

int get(char c) {
    if (c == 'E') return 0;  // 东
    if (c == 'S') return 1;  // 南  
    if (c == 'W') return 2;  // 西
    return 3;                // 北
}

2. 坐标编码

int getid(int x, int y) {
    return (x - 1) * m + y;  // 二维转一维
}

3. 建图

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i][j] != 'X') {  // 非障碍物
            int d = get(a[i][j]), id = getid(i, j);
            
            for (int k = 0; k < 4; k++) {  // 四个方向
                int x = i + dx[k], y = j + dy[k];
                
                if (x >= 1 && x <= n && y >= 1 && y <= m)  // 边界检查
                    Addedge(id, getid(x, y), 
                           d <= k ? k - d : 4 - d + k);
            }
        }

4. 最短路计算

使用优先队列优化的 Dijkstra 算法：

void dij() {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pair<int, int>> pq;
    dis[1] = 0, pq.emplace(0, 1);
    
    while (!pq.empty()) {
        int x = pq.top().second; pq.pop();
        if (v[x]) continue;
        v[x] = 1;
        
        for (auto [y, w] : e[x]) 
            if (!v[y] && dis[x] + w < dis[y])
                dis[y] = dis[x] + w, pq.emplace(-dis[y], y);
    }
}

复杂度分析

• 时间复杂度：$O((nm)\log(nm))$

  • 节点数：$n \times m$
  • 每个节点最多4条边
  • Dijkstra 复杂度：$O(E\log V)$

• 空间复杂度：$O(nm)$

  • 邻接表存储图结构
  • 距离数组和访问标记

样例分析

样例1

输入：
3 3
EES
SSW  
ESX

输出：3

解释：最优方案需要旋转3次，如将(1,2)的W旋转3次变为S。

样例2

输入：
3 3
EES
SSW
EEX

输出：0

解释：无需旋转即可到达终点。

代码实现细节

边界处理

// 方向数组：东、南、西、北
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

// 边界检查
if (x >= 1 && x <= n && y >= 1 && y <= m)

障碍物处理

if (a[i][j] != 'X')  // 只在非障碍物上建边

终点特殊处理

题目保证终点为'X'，因此终点没有出边，只能作为路径的终点。

总结

本题的关键在于：

1. 问题转化：将箭头旋转问题转化为图论最短路问题
2. 代价计算：正确计算不同方向间的旋转代价
3. 高效算法：使用 Dijkstra 算法保证最优解

这种建模方法在解决状态转移代价类问题时非常有效，特别是当状态转移可以量化为边权时。