中国海洋大学第四届朗讯杯高级组 Cash Cow（模拟）

题目：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2721

题意：给定n个左标，跟那n个坐标相同的且3个以上的消失，圈都靠下，而且如果一整列都没有的话，就都往左靠。。。。

思路：比赛的时候没调试完，，，，最坑爹的是，用后台数据测试都对了，结果还是wrong, 经过鑫哥指导。。。那些字符要以字符串的形式输入，

否则会wrong ,后台的原因不知道为什么。。。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 using namespace std;

 int dx[]= {,-,,};

 int dy[]= {,,,-};

 char G[][],map[][];

 struct node

 {

     int x,y;

 }a[];

 struct point

 {

     int x,y;

 }pos,next;

 void bfs(int x1,int y1)

 {

     int i,j,k,count=;

     int vis[][];

     char ch;

     char f;

     f='a';

     memset(vis,,sizeof(vis));

     ch=G[x1][y1];

     queue<point>q;

     next.x=x1;

     next.y=y1;

     vis[x1][y1]=;

     q.push(next);

     while(!q.empty())

     {

         pos=q.front();

         q.pop();

         count++;

         for(i=; i<; i++)

         {

             next.x=pos.x+dx[i];

             next.y=pos.y+dy[i];

             if(!vis[pos.x+dx[i]][pos.y+dy[i]]&&G[pos.x+dx[i]][pos.y+dy[i]]==ch&&

                     pos.x+dx[i]>=&&pos.x+dx[i]<=&&pos.y+dy[i]>=&&pos.y+dy[i]<=)

             {

                 vis[pos.x+dx[i]][pos.y+dy[i]]=;

                 q.push(next);

             }

         }

     }

     if(count>=)//刚开始 没看到这句with a cluster of 3 or more circles,

     {

         for(i=; i<=; i++)

         for(j=; j<=; j++)

         if(vis[i][j]==)

         G[i][j]=f;

     }

     for(i=; i<=; i++)

     {

         for(j=; j>=; j--)//一定要倒着来，因为这个调试了好长时间。。。

         {

             if(G[i][j]==f)

             {

                 for(k=j; k<=; k++)

                 {

                     G[i][k]=G[i][k+];

                     G[i][k+]=f;

                 }

             }

         }

     }

     for(i=; i>=; i--)//一定要倒着来，因为这个调试了好长时间。。。

     {

         if(G[i][]==f)

         {

             for(j=i; j<=; j++)

                 for(k=; k<=; k++)

                 {

                     G[j][k]=G[j+][k];

                     G[j+][k]=f;

                 }

         }

     }

 }

 int main()

 {

     int n,i,j,sum;

     char ch;

     char f;

     f='a';

     while(scanf("%d%*c",&n)!=EOF&&n)

     {

         sum=;

         memset(G,,sizeof(G));

         memset(map,,sizeof(map));

         for(i=; i>=; i--)

         cin>>map[i];

         for(i=; i>=; i--)

         {

             for(j=; j<=; j++)

             G[j][i]=map[i][j-];

         }

         for(i=; i<n; i++)

         {

              cin>>ch>>a[i].y;

             a[i].x=ch-;

             if(G[a[i].x][a[i].y]!=f)

             bfs(a[i].x,a[i].y);

         }

         for(i=; i<=; i++)

             for(j=; j<=; j++)

                 if(G[i][j]!=f)

                     sum++;

         printf("%d\n",sum);

     }

     return ;

 }

巴特西

中国海洋大学第四届朗讯杯高级组 Cash Cow（模拟）

最新文章

热门文章