题目理解

我们有一个 n×m 的棋盘，棋盘上有四种类型的边（0:不通，1:普通道路，2:直行道路，3:互通道路）。棋子有颜色和等级，每次在空位放一个棋子，然后问从这个棋子出发，按照规则能走到多少个不同的位置（包括吃子）。

规则总结：

1. 路径必须沿着同类型边
2. 不能经过重复位置
3. 不能穿过其他棋子
4. 吃子时只能吃不同颜色且等级≤自己的棋子

核心难点

1. 边类型限制：

   • 类型1：最多走1条边
   • 类型2：只能沿直线走任意条，不能转弯
   • 类型3：可以任意走，任意转弯

2. 数据规模大：n×m ≤ 2×10^5, q ≤ 10^5，需要高效算法

思路分析

由于数据规模大，我们需要对每种边类型分别处理，并利用并查集或BFS的优化。

对类型3边（互通道路）

这些边连接的区域可以自由走动，我们可以用并查集把通过类型3边连通的空位合并。

• 每个连通分量记录：棋子数量、最高等级的黑棋、最高等级的白棋
• 当新放棋子时，检查它所在的互通区域能到达哪些其他互通区域

对类型2边（直行道路）

从起点向四个方向扩展，直到遇到：

• 边界
• 非类型2边
• 有棋子的位置（检查是否能吃）

对类型1边（普通道路）

只能走一步，直接检查四个方向上是否有类型1边且目标位置可到达。

算法步骤

1. 预处理类型3的连通块

   • 用并查集连接所有通过类型3边相连的空位
   • 记录每个连通块的信息

2. 处理每个新棋子

   • 初始化答案为0

   • 标记已访问的位置集合

   • 步骤A：处理类型3边

     • 把起点所在的互通连通块的所有空位加入答案
     • 检查连通块边界上通过类型1/2边能到达的位置

   • 步骤B：处理类型2边

     • 向四个方向直线扩展，遇到空位则加入答案，遇到棋子则检查是否能吃

   • 步骤C：处理类型1边

     • 检查起点四个方向上的类型1边，目标位置如果是空位或可吃的棋子则加入答案

3. 去重

   • 用数组标记已访问位置，避免重复计数

代码框架

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

const int MAXN = 200005;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
};

int n, m, q;
vector<string> horizontal, vertical; // 存储横向和纵向边的类型
vector<int> board; // 存储每个位置的棋子信息
vector<int> color, level; // 棋子颜色和等级

// 并查集用于类型3连通块
vector<int> parent, sz;
vector<set<int>> comp_edges; // 连通块边界信息

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
        // 合并边界信息...
    }
}

// 位置编码
int encode(int x, int y) {
    return (x-1)*m + (y-1);
}

void solve() {
    cin >> n >> m >> q;
    
    horizontal.resize(n);
    vertical.resize(n-1);
    board.assign(n*m, -1);
    color.resize(q);
    level.resize(q);
    
    // 读入边信息
    for (int i = 0; i < n; i++) {
        cin >> horizontal[i];
    }
    for (int i = 0; i < n-1; i++) {
        cin >> vertical[i];
    }
    
    // 初始化类型3的并查集
    parent.resize(n*m);
    sz.assign(n*m, 1);
    for (int i = 0; i < n*m; i++) {
        parent[i] = i;
    }
    
    // 连接类型3边
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 检查右边
            if (j < m && horizontal[i-1][j-1] == '3') {
                unite(encode(i,j), encode(i,j+1));
            }
            // 检查下边
            if (i < n && vertical[i-1][j-1] == '3') {
                unite(encode(i,j), encode(i+1,j));
            }
        }
    }
    
    // 处理每个询问
    for (int i = 0; i < q; i++) {
        int col, lv, x, y;
        cin >> col >> lv >> x >> y;
        color[i] = col;
        level[i] = lv;
        
        int pos = encode(x, y);
        board[pos] = i; // 放置棋子
        
        // 计算能到达的位置数量
        int ans = 0;
        vector<bool> visited(n*m, false);
        
        // 1. 处理类型3连通块
        int comp = find(pos);
        // 这里需要遍历连通块中的所有空位...
        
        // 2. 处理类型2边
        for (int d = 0; d < 4; d++) {
            int nx = x, ny = y;
            while (true) {
                nx += dx[d];
                ny += dy[d];
                if (nx < 1 || nx > n || ny < 1 || ny > m) break;
                
                // 检查边类型
                char edge_type;
                if (dx[d] == 0) { // 横向
                    int miny = min(y, ny);
                    edge_type = horizontal[x-1][miny-1];
                } else { // 纵向
                    int minx = min(x, nx);
                    edge_type = vertical[minx-1][y-1];
                }
                
                if (edge_type != '2') break;
                
                int npos = encode(nx, ny);
                if (board[npos] == -1) {
                    // 空位
                    if (!visited[npos]) {
                        visited[npos] = true;
                        ans++;
                    }
                } else {
                    // 有棋子，检查是否能吃
                    int idx = board[npos];
                    if (color[idx] != col && level[idx] <= lv) {
                        if (!visited[npos]) {
                            visited[npos] = true;
                            ans++;
                        }
                    }
                    break; // 遇到棋子停止
                }
            }
        }
        
        // 3. 处理类型1边
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            
            char edge_type;
            if (dx[d] == 0) { // 横向
                int miny = min(y, ny);
                edge_type = horizontal[x-1][miny-1];
            } else { // 纵向
                int minx = min(x, nx);
                edge_type = vertical[minx-1][y-1];
            }
            
            if (edge_type != '1') continue;
            
            int npos = encode(nx, ny);
            if (board[npos] == -1) {
                // 空位
                if (!visited[npos]) {
                    visited[npos] = true;
                    ans++;
                }
            } else {
                // 有棋子
                int idx = board[npos];
                if (color[idx] != col && level[idx] <= lv) {
                    if (!visited[npos]) {
                        visited[npos] = true;
                        ans++;
                    }
                }
            }
        }
        
        cout << ans << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}

复杂度分析

• 预处理类型3连通块：O(n×m)
• 每个查询：
  • 类型2边扩展：O(直线长度) ≈ O(n+m)
  • 类型1边：O(1)
  • 类型3连通块遍历：O(连通块大小)
• 总体可以接受

优化点

1. 对类型3连通块，可以预处理每个连通块的所有位置
2. 使用更高效的数据结构记录棋子信息
3. 对类型2边的扩展进行记忆化

这个解法能够处理大规模数据，并通过分类处理不同边类型来满足题目要求。