几个样例：
5 5
wCCww
wCC..
..w..
....w
ww..w
Returns: 0
3 3
C.w
...
.C.
Returns: 1
21 20
CC..CCCw.CwC..CC.w.C
C.CCCwCCC.w.w..C.w..
wwww...CC.wC.Cw.CC..
CC..CC.w..w.C..CCCC.
CC.CCC..CwwCCC.wCC..
w.C..wwCC.CC.wwwCC..
.CC.CC..CCC..CC.CC.C
Cw....C.C.CCC...CC..
CC.C..Cww.C.CwwwC..w
wCCww..C...CCCCCCC.w
C.CCw.CC.ww...C.CCww
C.C.C.CCwCC..wCCw.Cw
CCC.C...w..C.wC.wCCw
CC.C..C..CCC.CC.C...
C.ww...CCC..CC...CCC
...CCC.CwwwC..www.C.
wwCCCCC.w.C.C...wCwC
CCwC.CwCCC.C.w.Cw...
C.w.wC.CC.CCC.C.w.Cw
CCw.CCC..C..CC.CwCCw
C.wwwww.CwwCCwwwwwww
Returns: 9
分析：非常好的一道题！
这道题和bzoj3171非常像.是一类容量表示限制的题,即要求的东西有许多限制，通过限定容量大小来满足这些限制. 因为和容量大小有关，所以这些限制一般为数字上的限制.
遇到这类题该怎么做呢？
1.题目肯定会让你求满足条件的情况下的最值.首先要分析得到怎么样才能满足条件,一定要找到数字关系！
2.容量大小代表数字限制，建一个直观的最大流模型.
3.拆点，将有花费的操作连成对应的有费用的边.
如何建呢？
首先找到初始状态，即所有边都是没有任何费用的. 例如bzoj3171题目中给出的箭头，本题中将所有的轨道变成弯的就是初始状态了. 接着找到需要费用的边. 例如bzoj3171中的更改箭头方向，本题中的将一个弯的轨道变成直的轨道（有弯星人在上面的）. 最后检查建出来的图是否满足要求：存在对应关系:满足限制即满流.
对于这道题而言，每一个空地必须伸出两个轨道，每个点有直的铁轨和弯的铁轨.
直的铁轨即，一块空地连出两条横向或纵向的轨道。弯的铁轨即，一块空地连出一条横向和一条纵向的轨道。
一个点两种不同的类别，这启示我们拆点分类.对于每一个点拆成两个点，一个是横着的点，伸出两个横着的轨道，一个是竖着的点，伸出两个竖着的轨道.它们都只和相邻的没有障碍的点拆出来的对应点相连,容量为1，费用为0
有费用的边即同一个点拆出来的两个点，如果这个点上有弯星人，它们之间的费用则为1，否则为0,容量为1.
那么和源汇的边要怎么处理呢？
错误的做法：一个点既连源点又连汇点. 显然这样源点会直接通过这个点走到汇点,不行.
正确的做法是黑白染色！相当于把图看作二分图. 对于图上做网络流，连边的问题通常用这种方法解决.
事实上也不需要真的dfs去染色，只需要看行数+列数是奇数还是偶数即可.
最后要先判断是否满流，再来输出解.
挺好的题，将限制与容量联系起来，是一类较为常见的题型.get到了新姿势：黑白染色建图.
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
const int maxn = ,dx[] = {,,,-},dy[] = {,-,,},inf = 0x7fffffff;
int n,m,head[maxn],to[maxn * ],nextt[maxn * ],w[maxn * ],cost[maxn * ],tot = ;
int S,T,ans,anss,sum;
int vis[maxn],vis2[maxn],d[maxn];
char s[maxn][maxn]; void add(int x,int y,int z,int p)
{
cost[tot] = p;
w[tot] = z;
to[tot] = y;
nextt[tot] = head[x];
head[x] = tot++; cost[tot] = -p;
w[tot] = ;
to[tot] = x;
nextt[tot] = head[y];
head[y] = tot++;
} bool spfa()
{
for (int i = ; i <= T; i++)
d[i] = inf;
memset(vis,,sizeof(vis));
memset(vis2,,sizeof(vis2));
d[S] = ;
vis[S] = ;
queue <int> q;
q.push(S);
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = ;
for (int i = head[u];i;i = nextt[i])
{
int v = to[i];
if (w[i] && d[v] > d[u] + cost[i])
{
d[v] = d[u] + cost[i];
if (!vis[v])
{
vis[v] = ;
q.push(v);
}
}
}
}
return d[T] < inf;
} int dfs(int u,int f)
{
if (u == T)
{
ans += d[u] * f;
return f;
}
int res = ;
vis2[u] = ;
for (int i = head[u];i;i = nextt[i])
{
int v = to[i];
if (!vis2[v] && w[i] && d[v] == d[u] + cost[i])
{
int temp = dfs(v,min(f - res,w[i]));
w[i] -= temp;
w[i ^ ] += temp;
res += temp;
if (res == f)
return res;
}
}
return res;
} void dinic()
{
while (spfa())
anss += dfs(S,inf);
} int calc(int x,int y)
{
return (x - ) * m + y;
} int main()
{
scanf("%d%d",&n,&m);
S = n * m * + ;
T = S + ;
for (int i = ; i <= n; i++)
scanf("%s",s[i] + );
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++)
{
if (s[i][j] == 'w')
continue;
int temp = calc(i,j);
if ((i + j) % == )
{
sum += ;
add(S,calc(i,j),,);
add(S,calc(i,j) + n * m,,);
//横
if (j - > && s[i][j - ] != 'w')
add(calc(i,j),calc(i,j - ),,);
if (j + <= m && s[i][j + ] != 'w')
add(calc(i,j),calc(i,j + ),,);
//竖
if (i - > && s[i - ][j] != 'w')
add(calc(i,j) + n * m,calc(i - ,j) + n * m,,);
if (i + <= n && s[i + ][j] != 'w')
add(calc(i,j) + n * m,calc(i + ,j) + n * m,,);
}
else
{
add(calc(i,j),T,,);
add(calc(i,j) + n * m,T,,);
}
int p = ;
if (s[i][j] == 'C')
p = ;
add(calc(i,j),calc(i,j) + n * m,,p);
add(calc(i,j) + n * m,calc(i,j),,p);
}
dinic();
if (anss != sum)
ans = -;
printf("%d\n",ans); return ;
}