首页 > 代码库 > （BFS）UVA - 12529 Fix the Pond

（BFS）UVA - 12529 Fix the Pond

2024-10-05 01:08:01   217人阅读

题目链接

不知道怎么该评价这道题……首先题目给的形式就很坑，很大程度上变成了一个模拟题。实际上就是求初始联通块个数。答案即为联通快个数-1.

  1 #include <iostream>
  2 #include <string>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <queue>
  8 #include <set>
  9 #include <map>
 10 #include <list>
 11 #include <vector>
 12 #include <stack>
 13 #define mp make_pair
 14 //#define P make_pair
 15 #define MIN(a,b) (a>b?b:a)
 16 //#define MAX(a,b) (a>b?a:b)
 17 typedef long long ll;
 18 typedef unsigned long long ull;
 19 const int MAX=605;
 20 const int MAX_V=25;
 21 const int INF=2e9+5;
 22 const double M=4e18;
 23 using namespace std;
 24 const int MOD=1e9+7;
 25 typedef pair<ll,int> pii;
 26 const double eps=0.000000001;
 27 #define rank rankk
 28 char a[MAX][MAX];
 29 bool vi[MAX][MAX];
 30 int dx[4]={0,-1,0,1};
 31 int dy[4]={-1,0,1,0};
 32 int n,cnt;
 33 bool check(int x,int y)
 34 {
 35     return x>=1&&x<=2*n&&y>=1&&y<=2*n+1&&!vi[x][y];
 36 }
 37 void bfs(int sx,int sy)
 38 {
 39     vi[sx][sy]=true;
 40     queue<pii> que;
 41     que.push(mp(sx,sy));
 42     while(!que.empty())
 43     {
 44         int nx=que.front().first,ny=que.front().second;
 45 //        if(sx==1&&sy==1)
 46 //            printf("nx=%d ny=%d\n",nx,ny);
 47         que.pop();
 48         if(nx%2==0&&ny%2==0)
 49         {
 50             for(int i=0;i<4;i++)
 51             {
 52                 bool st=false;
 53                 int x1=nx+dx[i],y1=ny+dy[i];
 54                 if(check(x1,y1))
 55                 {
 56 //                    printf("%d %d\n",x1,y1);
 57                     if(i==0)
 58                         {if(nx==1||ny==1||a[nx-1][ny/2]==‘H‘)
 59                             st=true;}
 60                     else if(i==1)
 61                     {
 62                         if(nx==1||ny==1||a[nx-1][ny/2]==‘V‘)
 63                             st=true;
 64                     }
 65                     else if(i==2)
 66                     {
 67                         if(ny==1||nx==2*n||a[nx][ny/2]==‘H‘)
 68                             st=true;
 69                     }
 70                     else if(ny==1||nx==2*n||a[nx][ny/2]==‘V‘)
 71                         st=true;
 72                    if(st)
 73                     {
 74 //                        printf("!!\n");
 75                         que.push(mp(x1,y1));
 76                         vi[x1][y1]=true;
 77                     }
 78                 }
 79 
 80             }
 81         }
 82         else if(nx%2==0&&ny%2==1)
 83         {
 84             for(int i=0;i<4;i++)
 85             {
 86                 bool st=false;
 87                 int x1=nx+dx[i],y1=ny+dy[i];
 88                 if(check(x1,y1))
 89                 {
 90                     if(i==0)
 91                         {
 92                             if(nx==2*n||ny==1||a[nx][ny/2]==‘H‘)
 93                             st=true;
 94                         }
 95                     else if(i==1)
 96                     {
 97                         if(nx==1||ny==2*n+1||a[nx-1][(ny+1)/2]==‘V‘)
 98                             st=true;
 99                     }
100                     else if(i==2)
101                     {
102                         if(nx==1||ny==2*n+1||a[nx-1][(ny+1)/2]==‘H‘)
103                             st=true;
104                     }
105                     else if(nx==2*n||ny==1||a[nx][ny/2]==‘V‘)
106                             st=true;
107                 }
108                 if(st)
109                 {
110                     que.push(mp(x1,y1));
111                     vi[x1][y1]=true;
112                 }
113             }
114         }
115         else if(nx%2==1&&ny%2==0)
116         {
117             for(int i=0;i<4;i++)
118             {
119                 bool st=false;
120                 int x1=nx+dx[i],y1=ny+dy[i];
121                 if(check(x1,y1))
122                 {
123 //                    if(sx==1&&sy==1)
124 //                        printf("~~%d %d\n",x1,y1);
125                     if(i==0)
126                         {if(nx==2*n||ny==1||a[nx][ny/2]==‘H‘)
127                             st=true;}
128                     else if(i==1)
129                     {
130                         if(nx==1||ny==1||a[nx-1][ny/2]==‘V‘)
131                             st=true;
132                     }
133                     else if(i==2)
134                     {
135                         if(nx==1||ny==1||a[nx-1][ny/2]==‘H‘)
136                             st=true;
137                     }
138                     else if(nx==2*n||ny==1||a[nx][ny/2]==‘V‘)
139                         st=true;
140                 }
141                 if(st)
142                 {
143                     que.push(mp(x1,y1));
144                     vi[x1][y1]=true;
145                 }
146             }
147         }
148             else if(nx%2==1&&ny%2==1)
149         {
150             for(int i=0;i<4;i++)
151             {
152                 bool st=false;
153                 int x1=nx+dx[i],y1=ny+dy[i];
154                 if(check(x1,y1))
155                 {
156                     if(i==0)//向左走
157                         {if(nx==1||ny==1||a[nx-1][ny/2]==‘H‘)
158                             st=true;
159                         }
160                     else if(i==1)//向上走
161                     {
162                         if(nx==1||ny==1||a[nx-1][ny/2]==‘V‘)
163                             st=true;
164                     }
165                     else if(i==2)//向右走
166                     {
167                         if(ny==2*n+1||nx==2*n||a[nx][(ny+1)/2]==‘H‘)
168                             st=true;
169                     }
170                     else if(i==3)
171                     {
172 //                        if(nx==1&&ny==1)
173 //                        {
174 //                            printf("%d %d %c\n",nx,(ny+1)/2,a[nx][(ny+1)/2]);
175 //                            printf("%d?= %d\n",2n+1,)
176 //                            if(st)
177 //                                printf("sb\n");
178 //                        }
179                         if(ny==2*n+1||nx==2*n||a[nx][(ny+1)/2]==‘V‘)//向下走
180                             st=true;
181 
182                     }
183                     if(st)
184                     {
185                         que.push(mp(x1,y1));
186                         vi[x1][y1]=true;
187                     }
188                 }
189 
190             }
191         }
192     }
193 }
194 int main()
195 {
196     while(~scanf("%d",&n))
197     {
198         memset(vi,false,sizeof(vi));
199         cnt=0;
200         for(int i=1;i<=2*n-1;i++)
201             scanf("%s",a[i]+1);
202         for(int i=1;i<=2*n;i++)
203         {
204             for(int j=1;j<=2*n+1;j++)
205             {
206                 if(vi[i][j])
207                     continue;
208 //                printf("!%d %d\n",i,j);
209                 ++cnt;
210                 bfs(i,j);
211             }
212         }
213         printf("%d\n",cnt-1);
214     }
215 }

 

（BFS）UVA - 12529 Fix the Pond


联系
我们