很厉害的题啊。差点就做出来了。

首先看到题意之后会有一个网络流想法：将网格中每个节点，向四个方向连流量为 的边， 连向蓝色接口，红色接口连向 ，图中最大流就是答案。

直接最大流显然做不得，考虑将最大流转化为最小割。通过割最少的边来让红蓝不连通。

我们观察割的过程，首先肯定不会存在一个接口既不与 连通也不与 连通，所以每种接口可以按与 连与 连分成两种颜色，我们也称其为蓝和红，这样，如果原来的某个红色接口与 之间的边被割了，我们就认为它改变了颜色，花费 的代价。网格图中间的节点，成为哪种颜色都没代价。那么此时的蓝色和红色，就分别指代与 和与 连通的点集。

观察两个颜色不同的图中节点，我们在其中间连一条割线，那么割线组成的所有路径就把平面分成了若干块，代价为割线长度总和。我们观察割线组成的路径有什么性质。

首先肯定不会有封闭的环，这个是很显然的，要不然我们可以直接把环中的颜色改变，这一步没代价，但是这个环没了，代价减小。

其次，肯定不会有连接同一个边界上两个点或者相邻边界上两点的路径，否则也可以把中间颜色全部改变，把路径消掉，手玩易得代价变化量不超过 ，不会增大。

最后也是最关键的性质：任何一条割线组成的路径不会拐弯。 如果拐弯了完全可以掰直，代价也不会变。

也就是说，割线只可能从第 行的左端点连向第 行的右端点，或者第 列上端点连向第 列下端点。

那么我们可以分类讨论是连行还是连列，以连行为例。设 表示做到第 行，第 行颜色为蓝/红的最小代价，容易从 转移到 。这样 H1 就可以 做完了。

至于 H2，因为 DP 的第二维很小，用线段树动态维护转移矩阵即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,m,Q;
char U[N],D[N],L[N],R[N];
int dp[N][2];
int main() {
	cin >> n >> m >> Q;
	cin >> (L + 1);
	cin >> (R + 1);
	cin >> (U + 1);
	cin >> (D + 1);
	int ans = 1e9;
	for(int i = 0;i <= m;i++) dp[i][0] = dp[i][1] = 1e9;
	dp[1][0] = (U[1] != 'B') + (D[1] != 'B');
	dp[1][1] = (U[1] != 'R') + (D[1] != 'R');
	for(int i = 1;i <= n;i++)
		dp[1][0] += (L[i] != 'B'),dp[1][1] += (L[i] != 'R');
	for(int i = 2;i <= m;i++) {
		dp[i][0] = min(dp[i - 1][0],dp[i - 1][1] + n) + (U[i] != 'B') + (D[i] != 'B');
		dp[i][1] = min(dp[i - 1][1],dp[i - 1][0] + n) + (U[i] != 'R') + (D[i] != 'R');
	}
	for(int i = 1;i <= n;i++) dp[m][0] += (R[i] != 'B'),dp[m][1] += (R[i] != 'R');
	ans = min({ans,dp[m][0],dp[m][1]});
	for(int i = 0;i <= n;i++) dp[i][0] = dp[i][1] = 1e9;
	dp[1][0] = (L[1] != 'B') + (R[1] != 'B');
	dp[1][1] = (L[1] != 'R') + (R[1] != 'R');
	for(int i = 1;i <= m;i++)
		dp[1][0] += (U[i] != 'B'),dp[1][1] += (U[i] != 'R');
	for(int i = 2;i <= n;i++) {
		dp[i][0] = min(dp[i - 1][0],dp[i - 1][1] + m) + (L[i] != 'B') + (R[i] != 'B');
		dp[i][1] = min(dp[i - 1][1],dp[i - 1][0] + m) + (L[i] != 'R') + (R[i] != 'R');
	}
	for(int i = 1;i <= m;i++) dp[n][0] += (D[i] != 'B'),dp[n][1] += (D[i] != 'R');
	ans = min({ans,dp[n][0],dp[n][1]});
	cout << ans << endl;
	return 0;
}