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,L<=15

 

原题题意即为将图转化成每个点入度出度恰好为1

拆点，拆成入点和出点

向本来指向的边连费用为0的边

向周围的边连费用为1的边

 

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #define id(x,y) (x-1)*m+y  7 #define N (10000+10)  8 #define M (1000000+10)  9 using namespace std; 10 bool used[N]; 11 int n,m,s,e,z,Ans,a[101][101]; 12 int num_edge,head[N]; 13 int dis[N],INF,pre[N]; 14 int dx[5]= {
   0,-1,1,0,0},dy[5]= {
   0,0,0,-1,1}; 15 char st[101]; 16 queue
          
           q; 17 struct node 18 { 19 int to,next,Flow,Cost; 20 } edge[M*2]; 21 22 void add(int u,int v,int l,int c) 23 { 24 edge[++num_edge].to=v; 25 edge[num_edge].next=head[u]; 26 edge[num_edge].Flow=l; 27 edge[num_edge].Cost=c; 28 head[u]=num_edge; 29 } 30 31 bool Spfa(int s,int e) 32 { 33 memset(dis,0x7f,sizeof(dis)); 34 memset(pre,-1,sizeof(pre)); 35 dis[s]=0; 36 used[s]=true; 37 q.push(s); 38 while (!q.empty()) 39 { 40 int x=q.front(); 41 q.pop(); 42 for (int i=head[x]; i!=0; i=edge[i].next) 43 if (dis[x]+edge[i].Cost
           
            0) 44 { 45 dis[edge[i].to]=dis[x]+edge[i].Cost; 46 pre[edge[i].to]=i; 47 if (!used[edge[i].to]) 48 { 49 used[edge[i].to]=true; 50 q.push(edge[i].to); 51 } 52 } 53 used[x]=false; 54 } 55 return dis[e]!=INF; 56 } 57 58 int MCMF(int s,int e) 59 { 60 int Fee=0; 61 while (Spfa(s,e)) 62 { 63 int d=INF; 64 for (int i=e; i!=s; i=edge[((pre[i]-1)^1)+1].to) 65 d=min(d,edge[pre[i]].Flow); 66 for (int i=e; i!=s; i=edge[((pre[i]-1)^1)+1].to) 67 { 68 edge[pre[i]].Flow-=d; 69 edge[((pre[i]-1)^1)+1].Flow+=d; 70 } 71 Fee+=d*dis[e]; 72 } 73 return Fee; 74 } 75 76 int main() 77 { 78 memset(&INF,0x7f,sizeof(INF)); 79 s=0,e=10001; 80 scanf("%d%d",&n,&m); 81 for (int i=1; i<=n; ++i) 82 { 83 scanf("%s",st); 84 for (int j=1; j<=m; ++j) 85 { 86 if (st[j-1]=='U') a[i][j]=1; 87 if (st[j-1]=='D') a[i][j]=2; 88 if (st[j-1]=='L') a[i][j]=3; 89 if (st[j-1]=='R') a[i][j]=4; 90 add(s,id(i,j),1,0); 91 add(id(i,j),s,0,0); 92 add(id(i,j)+m*n,e,1,0); 93 add(e,id(i,j)+m*n,0,0); 94 } 95 } 96 for (int i=1; i<=n; ++i) 97 for (int j=1; j<=m; ++j) 98 for (int k=1; k<=4; ++k) 99 {100 int x=i+dx[k],y=j+dy[k];101 if (x<1) x=n;102 if (x>n) x=1;103 if (y<1) y=m;104 if (y>m) y=1;105 add(id(i,j),id(x,y)+m*n,1,(k!=a[i][j]));106 add(id(x,y)+m*n,id(i,j),0,-(k!=a[i][j]));107 }108 printf("%d",MCMF(s,e));109 }