题目理解

问题背景

• 有一个 $n \times m$ 的网格图，顶点从 $(0,0)$ 到 $(n,m)$
• 边表示墙，初始时矩形边界一定存在墙
• 三种操作：添加墙、删除墙、查询左手扶墙法能否从起点走到终点

关键点

1. 坐标系：$(i,j)$ 表示第 $i+1$ 行第 $j+1$ 列，左上角是 $(0,0)$，右下角是 $(n,m)$
2. 墙的表示：只能连接相邻顶点（曼哈顿距离为1）
3. 左手扶墙法：始终保持左手接触墙面前进

算法思路

核心思想

左手扶墙法本质上是沿着墙面的外边界行走。我们可以把问题转化为在有向图中模拟行走过程。

状态表示

用有向边 $(x_0,y_0,x_1,y_1)$ 表示当前行走的方向，同时记录法珞在墙的哪一侧。

方向处理

对于每个有向边，我们需要确定下一个行走的边。优先级规则：

1. 左转（相对于当前前进方向）
2. 直行
3. 右转
4. 回头

具体实现步骤

1. 数据结构

// 存储墙的存在性
set<pair<pair<int,int>, pair<int,int>>> walls;

// 方向数组：上、右、下、左
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

2. 墙的维护

• 添加墙：向集合中插入对应的边（两个方向）
• 删除墙：从集合中删除对应的边

3. 查询操作模拟

对于每个查询：

1. 确定起点和终点的有向边状态
2. 从起点开始模拟行走
3. 记录路径长度，如果回到起点则输出-1

代码框架

#include <bits/stdc++.h>
using namespace std;

struct State {
    int x, y, dir;  // 当前位置和方向
    bool operator==(const State& other) const {
        return x == other.x && y == other.y && dir == other.dir;
    }
};

class Solution {
private:
    int n, m;
    set<pair<pair<int,int>, pair<int,int>>> walls;
    
    // 方向：0上, 1右, 2下, 3左
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    
    // 检查是否存在墙
    bool hasWall(int x1, int y1, int x2, int y2) {
        return walls.count({{x1,y1}, {x2,y2}}) || walls.count({{x2,y2}, {x1,y1}});
    }
    
    // 获取下一个方向（左手扶墙法）
    int getNextDir(int x, int y, int dir) {
        // 优先级：左转 -> 直行 -> 右转 -> 回头
        for (int i = -1; i <= 2; i++) {
            int ndir = (dir + i + 4) % 4;
            int nx = x + dx[ndir], ny = y + dy[ndir];
            // 检查是否在边界内且有墙
            if (nx >= 0 && nx <= n && ny >= 0 && ny <= m && hasWall(x, y, nx, ny)) {
                return ndir;
            }
        }
        return -1; // 无路可走
    }
    
public:
    void solve() {
        cin >> n >> m >> q;
        
        // 读取初始垂直墙
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m-1; j++) {
                int has;
                cin >> has;
                if (has) {
                    walls.insert({{i,j}, {i+1,j}});
                    walls.insert({{i+1,j}, {i,j}});
                }
            }
        }
        
        // 读取初始水平墙
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < m; j++) {
                int has;
                cin >> has;
                if (has) {
                    walls.insert({{i,j}, {i,j+1}});
                    walls.insert({{i,j+1}, {i,j}});
                }
            }
        }
        
        // 处理操作
        while (q--) {
            int op;
            cin >> op;
            if (op == 1) {
                // 添加墙
                int x0, y0, x1, y1;
                cin >> x0 >> y0 >> x1 >> y1;
                walls.insert({{x0,y0}, {x1,y1}});
                walls.insert({{x1,y1}, {x0,y0}});
            } else if (op == 2) {
                // 删除墙
                int x0, y0, x1, y1;
                cin >> x0 >> y0 >> x1 >> y1;
                walls.erase({{x0,y0}, {x1,y1}});
                walls.erase({{x1,y1}, {x0,y0}});
            } else {
                // 查询
                int x0, y0, x1, y1, d0, x2, y2, x3, y3, d1;
                cin >> x0 >> y0 >> x1 >> y1 >> d0 >> x2 >> y2 >> x3 >> y3 >> d1;
                
                // 确定起点和终点的有向边状态
                // 这里需要根据d0,d1确定具体的方向
                // 模拟行走过程...
                
                // 输出结果
                cout << simulate(x0, y0, x1, y1, d0, x2, y2, x3, y3, d1) << endl;
            }
        }
    }
    
    double simulate(int x0, int y0, int x1, int y1, int d0, 
                   int x2, int y2, int x3, int y3, int d1) {
        // 实现行走模拟
        // 返回路径长度，无法到达返回-1
        return -1; // 示例返回值
    }
};

复杂度分析

• 空间复杂度：$O(nm)$ 存储墙的信息
• 时间复杂度：
  • 添加/删除墙：$O(\log nm)$
  • 查询操作：最坏 $O(nm)$（遍历整个墙面）

优化方向

1. 状态压缩：用位运算优化方向判断
2. 记忆化：对于重复查询可以缓存结果
3. 提前终止：如果回到起点则立即返回-1

总结

这道题的关键在于理解左手扶墙法的行走规则，并将其转化为有向图上的路径搜索问题。通过维护墙的集合和模拟行走过程，可以有效地解决各种操作。