题意理解

我们有一个 N x M 的网格，格子上可能有：

• .：空地
• A, V, <, >：箭塔，分别表示朝上、下、左、右
• 1 ~ 9：箭靶，数字代表分数

规则：

1. 每个箭塔可以选择它所指方向上的任意一个箭靶，也可以不攻击。
2. 箭塔的攻击范围内不会有其他箭塔（即箭塔之间不会互相阻挡）。
3. 所有箭塔的攻击轨迹在地面的投影不能在任意格子相交（即不同箭塔的攻击路径不能经过同一个格子）。

目标：选择一些箭靶，使得总得分最大，同时满足路径不相交。

---

问题转化

由于箭塔的攻击路径是直线（上下左右），且路径不能相交，这意味着：

• 每个格子最多只能被一条攻击路径经过。
• 路径不能交叉，也不能重叠。

这实际上是一个最大权独立集问题在某种特殊图上的形式：
每个箭塔可以连接它方向上的若干箭靶，但不同箭塔的路径不能共用格子。

---

思路分析

我们可以把问题建模成二分图匹配或网络流问题：

• 每个箭塔可以匹配它攻击范围内的箭靶，但匹配的路径不能有公共格子。
• 由于箭塔之间不会互相阻挡，所以每个箭塔的攻击路径是连续的，中间只有空地或箭靶，没有其他箭塔。

但是“路径不能相交”这个条件比较麻烦，它意味着我们不能简单地把每个箭塔和它可达的箭靶连边，因为两个箭塔的路径可能经过同一个格子。

---

关键观察

实际上，路径不相交意味着：
每个格子最多只能被一个箭塔的攻击路径使用。

因此，我们可以这样建模：

1. 把每个箭塔看作左部节点。
2. 把每个箭靶看作右部节点。
3. 箭塔和箭靶之间可以匹配，当且仅当它们之间的路径上的所有格子都没有被其他箭塔占用。

但直接这样判断很复杂，因为路径占用是全局的。

---

更简洁的方法

注意到数据范围：N, M <= 50，总格子数最多 2500，箭塔数量最多 2500，但实际很少。

我们可以用最大流最小割来建模：

• 源点 → 箭塔 → 路径格子 → 箭靶 → 汇点
• 每个箭塔只能选一条路径
• 每个格子只能被一条路径使用
• 每个箭靶只能被一个箭塔击中

具体建图方法：

1. 对每个箭塔，枚举它方向上的所有箭靶。
2. 对每个候选靶子，检查路径上的格子是否都是空地或该靶子本身。
3. 如果路径合法，则箭塔可以攻击该靶子，但需要占用路径上的所有格子。
4. 为了满足“每个格子只能被一条路径使用”，我们把格子也作为节点，容量为 1。

---

网络流建图

节点类型：

• 源点 S
• 箭塔节点 Tower_i
• 格子节点 Cell_{x,y}（拆点，入点 → 出点，容量 1，保证每个格子只用一次）
• 箭靶节点 Target_j（容量 1，因为一个靶子只能被击中一次）
• 汇点 T

边：

1. S → Tower_i：容量 1（每个箭塔只能攻击一个靶子）
2. Tower_i → Cell_in：如果该格子是路径上的格子（包括靶子），则连边，容量 1
3. Cell_out → Target_j：如果该格子是靶子，则连边，容量 1
4. Target_j → T：容量 1

但这样建图会很大，因为每个箭塔对每个靶子都要建一条路径上的所有格子链。

---

更简单的实现方法

由于数据规模小，我们可以用DFS + 状态压缩（如果箭塔数 ≤ 20）或者DFS + 回溯来暴力搜索。

但是这里箭塔最多 2500，不能直接暴力。

---

实际可行的方法

我们注意到，虽然箭塔多，但每个箭塔能攻击的靶子数量有限（最多一行或一列），并且路径不相交条件很强，实际上可匹配的靶子很少。

我们可以用二分图匹配：

• 左部：箭塔
• 右部：箭靶
• 边：存在当且仅当路径合法且路径上的格子没有被其他匹配占用

但“路径占用”是全局的，不能直接做。
我们可以用DFS搜索匹配顺序，每次选择一个箭塔，枚举它能攻击的靶子，检查路径是否与已选路径冲突，不冲突则选择，然后继续搜索。

这种方法在靶子少的时候可行，但最坏情况指数级。

---

正解：行列分离 + 最大流

这是类似“棋盘覆盖”问题的常用技巧：

• 把网格的每个格子看作一个节点，拆成“行点”和“列点”。
• 箭塔的攻击路径可以看作一行或一列上的一段。
• 路径不相交 → 每个格子只能属于一条路径 → 每个格子节点容量为 1。

具体建图：

1. 对每个箭塔，从源点连一条容量 1 的边到它。
2. 对每个箭塔，向它攻击方向上的所有格子（直到靶子或边界）连边，容量 1。
3. 每个格子拆成入点和出点，入点 → 出点 容量 1。
4. 如果格子是靶子，则从格子出点连到该靶子节点，容量 1。
5. 每个靶子节点连到汇点，容量 1。

这样，流从 S → 箭塔 → 格子入 → 格子出 → 靶子 → T，保证了路径不重叠，且每个靶子只能被击中一次。

---

实现细节

• 箭塔和靶子都要编号。
• 格子拆点：in_id = x*M+y, out_id = N*M + x*M+y
• 靶子编号从 2*N*M 开始。
• 箭塔编号从 2*N*M + 靶子数量 开始。

---

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 55;
const int MAXV = 50010; // 节点数上限
const int INF = 1e9;

int N, M;
char grid[MAXN][MAXN];

// 网络流
struct Edge {
    int to, cap, rev;
};
vector<Edge> G[MAXV];
int level[MAXV], iter[MAXV];

void add_edge(int from, int to, int cap) {
    G[from].push_back({to, cap, (int)G[to].size()});
    G[to].push_back({from, 0, (int)G[from].size() - 1});
}

void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto &e : G[v]) {
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < (int)G[v].size(); i++) {
        Edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow = 0;
    while (true) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
}

// 节点编号分配
int cell_in_id(int x, int y) { return x * M + y; }
int cell_out_id(int x, int y) { return N * M + x * M + y; }

int target_id[MAXN][MAXN]; // 靶子编号
int tower_id[MAXN][MAXN];  // 箭塔编号

int dx[4] = {-1, 1, 0, 0}; // 上下左右
int dy[4] = {0, 0, -1, 1};
char tower_ch[4] = {'A', 'V', '<', '>'};

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> grid[i][j];
        }
    }

    // 编号分配
    int target_count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (grid[i][j] >= '1' && grid[i][j] <= '9') {
                target_id[i][j] = 2 * N * M + target_count;
                target_count++;
            }
        }
    }
    int tower_count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (grid[i][j] == 'A' || grid[i][j] == 'V' || grid[i][j] == '<' || grid[i][j] == '>') {
                tower_id[i][j] = 2 * N * M + target_count + tower_count;
                tower_count++;
            }
        }
    }

    int S = 2 * N * M + target_count + tower_count;
    int T = S + 1;
    int node_count = T + 1;

    // 建图
    // 格子拆点
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            add_edge(cell_in_id(i, j), cell_out_id(i, j), 1);
        }
    }

    // 箭塔 -> 路径格子 -> 靶子
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int dir = -1;
            for (int d = 0; d < 4; d++) {
                if (grid[i][j] == tower_ch[d]) {
                    dir = d;
                    break;
                }
            }
            if (dir == -1) continue;

            // 箭塔节点
            int tid = tower_id[i][j];
            add_edge(S, tid, 1);

            // 枚举路径
            int x = i + dx[dir], y = j + dy[dir];
            while (x >= 0 && x < N && y >= 0 && y < M) {
                if (grid[x][y] == 'A' || grid[x][y] == 'V' || grid[x][y] == '<' || grid[x][y] == '>') {
                    break; // 攻击范围内不会有其他箭塔
                }
                // 连接箭塔 -> 格子入点
                add_edge(tid, cell_in_id(x, y), 1);
                // 如果是靶子，连接格子出点 -> 靶子
                if (grid[x][y] >= '1' && grid[x][y] <= '9') {
                    int score = grid[x][y] - '0';
                    add_edge(cell_out_id(x, y), target_id[x][y], 1);
                    // 靶子 -> T 的边在下面统一加
                }
                x += dx[dir];
                y += dy[dir];
            }
        }
    }

    // 靶子 -> T
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (grid[i][j] >= '1' && grid[i][j] <= '9') {
                int score = grid[i][j] - '0';
                add_edge(target_id[i][j], T, score);
            }
        }
    }

    int ans = max_flow(S, T);
    cout << ans << endl;

    return 0;
}

---

总结

这个题的核心是把“路径不相交”转化为网络流中的节点容量限制，通过格子拆点来保证每个格子只被一条路径使用，从而用最大流求解最大得分。