lib/Documentation/docs-sonyckson/p4.cpp

   1 #include <vector>
   2 #include <set>
   3 #include <string>
   4 #include <fstream>
   5 #include <iostream>
   6 #include <iomanip>
   7 #include <map>
   8 #include <sstream>
   9 #include <queue>
  10 #include <algorithm>
  11
  12 #include <cmath>
  13 #include <cstdio>
  14 #include <cctype>
  15 #include <cstdlib>
  16 #include <cstring>
  17
  18 #define forn(i, n) for(int i=0;i<int(n);i++)
  19 #define FOR(i, a, b) for(int i=(a);i<int(b);i++)
  20 #define RFOR(i, b, a) for(int i=(b);i>int(a);i--)
  21 #define foreach(it, c)  for(__typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  22 #define ALL(x)   (x).begin(),(x).end()
  23 #define SIZE(x)   (int)(x).size()
  24 #define SORT(x) sort(ALL(x))
  25 using namespace std;
  26 #define VI vector<int>
  27 #define VS vector<string>
  28 #define PB push_back
  29 #define ISS istringstream
  30 #define OSS ostringstream
  31 typedef long long ll;
  32 // NUNCA DEFINIR int max....
  33 /* Max Flow */
  34 # include <stdio.h>
  35 # include <values.h>
  36
  37 # define MAXVERTICES 1802
  38 # define Q MAXVERTICES+1
  39
  40 # define min(a,b) (((a)<(b))? (a):(b))
  41 int rows, cols, p;
  42 int n;
  43 int f[MAXVERTICES][MAXVERTICES];
  44 int cf[MAXVERTICES][MAXVERTICES];
  45 int valor(int r, int c, int i){
  46         return (r*cols+c)*2+1+i;
  47 }
  48 vector<int> V;
  49 int dx[5] = {-1, 0, 1, 0, 0};
  50 int dy[5] = {0, 1, 0, -1, 0};
  51 int adentro(int r, int c ){ if( r >= 0 && c >= 0 && r < rows && c < cols ) return 1; return 0;}
  52 void setCapacity(void)
  53 {
  54         memset(cf, 0, sizeof(cf));
  55         int i ,j ,k;
  56         vector<string> vec;
  57         string s;
  58         V.clear();
  59         for(i=0;i<rows;i++){
  60                 cin >> s;
  61                 vec.PB(s);
  62         }
  63         n = 2*rows*cols+1;
  64
  65         for(i=0;i<rows;i++){
  66                 for(j=0;j<cols;j++){
  67                         if( vec[i][j] == '~' ) continue;
  68                         if( vec[i][j] == '*' ){
  69                                 V.push_back(valor(i,j,0));
  70                                 cf[0][valor(i,j,0)] = 1;
  71                                 cf[valor(i,j,0)][valor(i,j,1)] = 1;
  72                                 for(k=0;k<4;k++){
  73                                         int r, c;
  74                                         r = dx[k]+i;
  75                                         c = dy[k]+j;
  76                                         if(!adentro(r,c))continue;
  77                                         if( vec[r][c] != '~' && vec[r][c] != '*'){
  78                                                 cf[valor(i,j,1)][valor(r,c,0)] = 1;
  79                                         }
  80                                 }
  81                         }else
  82                         if( vec[i][j] == '@' ){
  83                                 cf[valor(i,j,0)][valor(i,j,1)] = 2000;
  84                                 for(k=0;k<4;k++){
  85                                         int r, c;
  86                                         r = dx[k]+i;
  87                                         c = dy[k]+j;
  88                                         if(!adentro(r,c))continue;
  89                                         if( vec[r][c] != '~' && vec[r][c] != '*'){
  90                                                 cf[valor(i,j,1)][valor(r,c,0)] = 2000;
  91                                         }
  92                                 }
  93                         }else
  94                         if( vec[i][j] == '.' ){
  95                                 cf[valor(i,j,0)][valor(i,j,1)] = 1;
  96                                 for(k=0;k<4;k++){
  97                                         int r, c;
  98                                         r = dx[k]+i;
  99                                         c = dy[k]+j;
 100                                         if(!adentro(r,c))continue;
 101                                         if( vec[r][c] != '~' && vec[r][c] != '*'){
 102                                                 cf[valor(i,j,1)][valor(r,c,0)] = 1;
 103                                         }
 104                                 }
 105                         }else
 106                         if( vec[i][j] == '#' ){
 107                                 cf[valor(i,j,0)][valor(i,j,1)] = 2000;
 108                                 cf[valor(i,j,1)][n] = p;
 109                                 for(k=0;k<4;k++){
 110                                         int r, c;
 111                                         r = dx[k]+i;
 112                                         c = dy[k]+j;
 113                                         if(!adentro(r,c))continue;
 114                                         if( vec[r][c] != '~' && vec[r][c] != '*'){
 115                                                 cf[valor(i,j,1)][valor(r,c,0)] = 2000;
 116                                         }
 117                                 }
 118                         }
 119                 }
 120         }
 121         /* get input and make the graph */
 122         /* 0 : source   ,    n : sink */
 123 }
 124 void initialize(void)
 125 {
 126         int i,j;
 127         for(i=0;i<=n;i++)
 128                 for(j=0;j<=n;j++){
 129                 f[i][j]=0;
 130                 }
 131 }
 132 int augment(void)
 133 {
 134         int q[Q],rear,front;
 135         int cost[MAXVERTICES],p[MAXVERTICES];
 136         int cfp,i,j;
 137         for(i=0;i<=n;i++)
 138                 cost[i]=p[i]=-1;
 139         cost[0]=0;
 140         rear=front=0;
 141         q[rear++]=0;
 142         while(rear!=front){
 143                 i=q[front++];
 144                 if(front==Q) front=0;
 145                 if(i==n) break;
 146                 if( i != 0 ){
 147                         int r, c;
 148                         r = ((i-1)/2)/cols;
 149                         c = ((i-1)/2)%cols;
 150                         for(int k = 0 ; k< 5; k ++ ){
 151                                 int rr = r+dx[k];
 152                                 int cc = c+dy[k];
 153                                 for(int h=0;h<2;h++){
 154                                         int j = valor(rr,cc, h);
 155                                         if(cf[i][j]>0 && cost[j]==-1){
 156                                                 cost[j]=cost[i]+1;
 157                                                 p[j]=i;
 158                                                 q[rear++]=j;
 159                                                 if(rear==Q) rear=0;
 160                                         }
 161                                 }
 162                         }
 163                         int j = n;
 164                         if(cf[i][j]>0 && cost[j]==-1){
 165                                 cost[j]=cost[i]+1;
 166                                 p[j]=i;
 167                                 q[rear++]=j;
 168                                 if(rear==Q) rear=0;
 169                         }
 170                         j = 0;
 171                         if(cf[i][j]>0 && cost[j]==-1){
 172                                 cost[j]=cost[i]+1;
 173                                 p[j]=i;
 174                                 q[rear++]=j;
 175                                 if(rear==Q) rear=0;
 176                         }
 177                 }else{
 178                         for(int h=0;h<V.size();h++){
 179                                 j = V[h];
 180                                 if(cf[i][j]>0 && cost[j]==-1){
 181                                         cost[j]=cost[i]+1;
 182                                         p[j]=i;
 183                                         q[rear++]=j;
 184                                         if(rear==Q) rear=0;
 185                                 }
 186                         }
 187                 }
 188         }
 189         if(cost[n]==-1) return 0;
 190         cfp=MAXINT;
 191         i=n;
 192         while(i){
 193                 cfp=min(cfp,cf[p[i]][i]);
 194                 i=p[i];
 195         }
 196         i=n;
 197         while(i){
 198                 f[p[i]][i]+=cfp;
 199                 f[i][p[i]]=-f[p[i]][i];
 200                 cf[p[i]][i]-=cfp;
 201                 cf[i][p[i]]+=cfp;
 202                 i=p[i];
 203         }
 204         return 1;
 205 }
 206 int maxFlow(void)
 207 {
 208         int i,totflow;
 209         setCapacity();
 210         initialize();
 211         while(augment());
 212         for(totflow=0,i=0;i<=n;i++)
 213                 totflow+=f[0][i];
 214         return totflow;
 215 }
 216 int main(){
 217         int i,j ,k;
 218         while(scanf("%i %i %i", &rows, &cols, &p)!= EOF){
 219                 printf("%i\n", maxFlow());
 220         }
 221         return 0;
 222 }