Description

一个循环格就是一个矩阵, 其中所有元素为箭头, 指向相邻四个格子. 每个元素有一个坐标 (行, 列), 其中左上角元素坐标为 \((0, 0)\). 给定一个起始位置 \((r, c)\), 你可以沿着箭头防线在格子间行走. 即如果 \((r, c)\) 是一个左箭头, 那么走到 \((r, c-1)\); 如果是右箭头那么走到 \((r, c+1)\); 如果是上箭头那么走到 \((r-1, c)\); 如果是下箭头那么走到 \((r+1, c)\); 每一行和每一列都是循环的, 即如果走出边界, 你会出现在另一侧.

一个完美的循环格是这样定义的: 对于任意一个起始位置, 你都可以 \(i\) 沿着箭头最终回到 起始位置. 如果一个循环格不满足完美, 你可以随意修改任意一个元素的箭头直到完美. 给定一个循环格, 你需要计算最少需要修改多少个元素使其完美.

Input

第一行两个整数 \(r, c\). 表示行和列, 接下来 \(r\) 行, 每行 \(c\) 个字符 LRUD, 表示 左右上下.

Output

一个整数, 表示最少需要修改多少个元素使得给定的循环格完美

Sample Input

3 4
RRRD
URLL
LRRR

Sample Output

2

Data Range

\(1 \leq r, c \leq 15\)

Explanation

首先看到数据范围就知道是最大流最小割或者状压动规这样的东西了~

结果发现一个点一定只会进一次, 出一次 (算上起点和终点), 所以就建最小割就可以了.

源点向每个点连容量 \(1\) 费用 \(0\) 的边

每个点拆出的点向汇点连容量 \(1\), 费用 \(0\) 的边

每个格子向四周连费用 \(0\) 或 \(1\) 的边

所以是不是很水呢~ 但是发现调了半天一直是零 (雾), 结果发现一个手残在 SPFA 里面把默认距离设成 dist[t] = infinity 而不是 dist[i] = infinity (循环里), 那就是我的问题了

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

using namespace std;
typedef long long lli;
const int maxn = 1010, maxm = 1000100, maxN = 30;
const lli infinit = 0x007f7f7f7f7f7f7fll;
const int x_mov[4] = {  0,  0, -1,  1 },
          y_mov[4] = { -1,  1,  0,  0 };

class SpfaMaxFlow
{
public:
    struct edge
    {
        int u, v;
        lli flow, cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm], *from[maxn];
    lli dist[maxn];
    bool inque[maxn];
    void add_edge(int u, int v, lli flow, lli cost)
    {
        // printf("add edge %d %d %lld %lld\n", u, v, flow, cost);
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool spfa(void)
    {
        queue<int> que;
        for (int i = 1; i <= n; i++)
            dist[i] = infinit, inque[i] = false, from[i] = NULL;
        que.push(s);
        dist[s] = 0, inque[s] = true;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next) {
                if (ep->flow && dist[p] + ep->cost < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->cost;
                    from[ep->v] = ep;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            }
            inque[p] = false;
        }
        if (dist[t] >= infinit)
            return false;
        return true;
    }
    lli max_flow, min_cost;
    void eval(void)
    {
        max_flow = 0;
        min_cost = 0;
        while (spfa()) {
            lli flow = infinit;
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                flow = min(flow, ep->flow);
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                ep->flow -= flow,
                ep->rev->flow += flow;
            max_flow += flow;
            min_cost += dist[t] * flow;
        }
        return ;
    }
} graph;

int n, m;
char str[maxN];
int arr[maxN][maxN];

int pos(int i, int j) {
    return (i-1) * m + j; }

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str + 1);
        for (int j = 1; j <= m; j++)
            switch (str[j]) {
                case 'L': arr[i][j] = 0; break;
                case 'R': arr[i][j] = 1; break;
                case 'U': arr[i][j] = 2; break;
                case 'D': arr[i][j] = 3; break;
                default: break;
            }
    }
    // Read data, building graph.
    graph.n = 2*n*m + 2;
    graph.s = graph.n - 1;
    graph.t = graph.n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k < 4; k++) {
                int x = i + x_mov[k],
                    y = j + y_mov[k];
                // Tranforming positions
                if (x > n) x = 1; if (x < 1) x = n;
                if (y > m) y = 1; if (y < 1) y = m;
                // Determination
                graph.add_edge(pos(i, j), pos(x, y) + n*m,
                    1, k == arr[i][j] ? 0 : 1);
            }
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            graph.add_edge(graph.s, pos(i, j), 1, 0);
            graph.add_edge(pos(i, j) + n*m, graph.t, 1, 0);
        }
    // Evaluation of result.
    graph.eval();
    lli res = graph.min_cost;
    printf("%lld\n", res);
    return 0;
}