Place the Robots 需要较强的建图能力

　　　　　　　　　　　　　　　　　　Place the Robots

思路：在任意一个点格子放机器人，那么它所在的行和列被控制了。我们对每一行或每一列连续的空地（草地忽视）称之为块，给每一行和每一列的块标号，

每一行的快与每一列的快相交的话，才有只有一个交点。我们把交点当边，把行块和列块连接起来。每一个空第都是一条边。详细细节见代码。

  1 #include <iostream>

  2 #include <cstdio>

  3 #include <cstring>

  4 #include <cmath>

  5 #include <algorithm>

  6 #include <string>

  7 #include <vector>

  8 #include <set>

  9 #include <map>

 10 #include <stack>

 11 #include <queue>

 12 #include <sstream>

 13 #include <iomanip>

 14 using namespace std;

 15 typedef long long LL;

 16 const int INF = 0x4fffffff;

 17 const double EXP = 1e-5;

 18 const int MS = 55;

 19 const int SIZE = 100005;

 20

 21 // data struct

 22 char pic[MS][MS];

 23 int sx[MS][MS];

 24 int sy[MS][MS];

 25

 26 int x[MS*MS];

 27 int y[MS*MS];

 28

 29 int cx[MS*MS];

 30 int cy[MS*MS];

 31

 32 bool edges[MS*MS][MS*MS];

 33 int mark[MS*MS];

 34 int nx,ny,kase;

 35 int n,m;

 36

 37 int path(int u)

 38 {

 39       for(int v=1;v<=ny;v++)

 40       {

 41             if(edges[u][v]&&!mark[v])

 42             {

 43                   mark[v]=1;

 44                   if(cy[v]==0||path(cy[v]))

 45                   {

 46                         cx[u]=v;

 47                         cy[v]=u;

 48                         return 1;

 49                   }

 50             }

 51       }

 52       return 0;

 53 }

 54

 55 void match()

 56 {

 57       memset(cx,0,sizeof(cx));

 58       memset(cy,0,sizeof(cy));

 59       int ans=0;

 60       for(int u=1;u<=nx;u++)

 61       {

 62             if(!cx[u])

 63             {

 64                   memset(mark,0,sizeof(mark));

 65                   ans+=path(u);

 66             }

 67       }

 68       printf("Case :%d\n%d\n",kase++,ans);

 69 }

 70

 71 int main()

 72 {

 73       kase=1;

 74       int T;

 75       scanf("%d",&T);

 76       while(T--)

 77       {

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

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

 80                   scanf("%s",pic[i]);

 81             memset(sx,0,sizeof(sx));

 82             memset(sy,0,sizeof(sy));

 83             int num=0,flag;

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

 85            {

 86                  flag=0;

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

 88                   {

 89                         if(pic[i][j]=='o')

 90                         {

 91                               if(flag==0)

 92                               {

 93                                     num++;

 94                                     flag=1;

 95                               }

 96                               sx[i][j]=num;

 97                         }

 98                         else if(pic[i][j]=='#')

 99                               flag=0;

100                   }

101            }

102             nx=num;

103             num=0;

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

105             {

106                   flag=0;

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

108                   {

109                         if(pic[i][j]=='o')

110                         {

111                               if(flag==0)

112                               {

113                                     num++;

114                                     flag=1;

115                               }

116                               sy[i][j]=num;

117                         }

118                         else if(pic[i][j]=='#')

119                               flag=0;

120                   }

121             }

122             ny=num;

123             memset(edges,0,sizeof(edges));

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

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

126             {

127                   if(pic[i][j]=='o')

128                         edges[sx[i][j]][sy[i][j]]=1;

129             }

130             match();

131       }

132       return 0;

133 }

巴特西

Place the Robots 需要较强的建图能力

最新文章

热门文章