传送门

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

HINT

1<=R,C<=15

这道题怎么做呢？我们很难想出怎么才是最优的决策走法，那么干脆不管他了！

这道题让我们想起了一个经典问题：“给出一个图，判断都少个点在至少一个环里面”。其中一种做法就是跑网络流，每一个点拆成两个，一个进，源点连向它，一个出，它连向汇点，然后跑一下最大流，就得到答案了。

这道题不是差不多嘛？

可以改道，那么我们就连成一张”四通八达”的图，原本的方向费用为0，其余的费用为1。跑一次费用流，答案就是费用了。

/**************************************************************

    Problem: 3171

    User: geng4512

    Language: C++

    Result: Accepted

    Time:4 ms

    Memory:1236 kb

****************************************************************/

#include<algorithm>

#include<cstdio>

#include<cstring>

#define INF 0x3f3f3f3f

#define MAXN 10005

using namespace std;

int n, m, S, T, dd[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

char mp[30][30];

int hsh[200];

struct Node { int v, w, f, nxt; } e[MAXN<<1];

int Adj[MAXN], ecnt = 1, cost, dis[MAXN];

int vis[MAXN];

inline void Add(int u, int v, int w, int f) {

    ++ ecnt; e[ecnt].v = v; e[ecnt].w = w; e[ecnt].f = f; e[ecnt].nxt = Adj[u]; Adj[u] = ecnt;

    ++ ecnt; e[ecnt].v = u; e[ecnt].w = -w; e[ecnt].f = 0; e[ecnt].nxt = Adj[v]; Adj[v] = ecnt;

}

bool Upd() {

    int tmp = INF;

    for(int u = 0; u <= T; ++ u) if(vis[u])

        for(int i = Adj[u]; i; i = e[i].nxt)

                if(!vis[e[i].v] && e[i].f)

                    tmp = min(tmp, dis[e[i].v] + e[i].w - dis[u]);

    if(tmp == INF) return 0;

    for(int u = 0; u <= T; ++ u) if(vis[u]) dis[u] += tmp;

    return 1;

}

int Aug(int u, int augco) {

    if(u == T) {

        cost += dis[S] * augco;

        return augco;

    }

    int augc = augco, delta, v;

    vis[u] = 1;

    for(int i = Adj[u]; i; i = e[i].nxt) {

        v = e[i].v;

        if(e[i].f && !vis[v] && dis[u] - e[i].w == dis[v]) {

            delta = Aug(v, min(e[i].f, augc));

            augc -= delta; e[i].f -= delta; e[i^1].f += delta;

            if(!augc) return augco;

        }

    }

    return augco - augc;

}

int ZKW() {

    do {

        do memset(vis, 0, sizeof vis); while(Aug(S, INF));

    } while(Upd());

    return cost;

}

int main() {

    scanf("%d%d", &n, &m);

    S = 2*n*m; T = S + 1;

    hsh['L'] = 3; hsh['R'] = 1; hsh['U'] = 2; hsh['D'] = 0;

    for(int i = 0; i < n; ++ i) {

        scanf("%s", mp[i]);

        for(int j = 0; j < m; ++ j) {

            Add(i*m+j, T, 0, 1);

            Add(S, i*m+j+n*m, 0, 1);

            for(int k = 0; k < 4; ++ k) {

                int x = i + dd[k][0], y = j + dd[k][1];

                if(x < 0) x = n-1;

                if(x == n) x = 0;

                if(y < 0) y = m-1;

                if(y == m) y = 0;

                Add(i*m+j+n*m, x*m+y, hsh[mp[i][j]] != k, 1);

            }

        }

    }

    printf("%d\n", ZKW());

}