Codeforces Round #575 (Div. 3) E. Connected Component on a Chessboard

客官°小女子只卖身不卖艺 2023-10-11 09:40 37阅读 0赞

[传送门][Link 1]

题意：

给你一个黑白相间的1e9\*1e9的棋盘，你需要从里面找出来由b个黑色的格子和w个白色的格子组成的连通器(就是你找出来的b+w个格子要连接在一起，不需要成环)。问你可不可以找出来，如果可以就先打印YES，再打印出所有格子的坐标，否则打印出NO。

![1633695-20190917103051936-695376743.png][]

题解：

[参考博客][Link 2]

如果b和w相等的时候，那么就可以用棋盘的一行来表示。

对于不相等的情况：

如果max(w,b)>min(w,b)\*3+1那么这样是找出不来符合条件的连通区域的。

看图中的红色部分你会知道只有这样十十的连接起来才是最大构成情况(这样写代码其实并不麻烦，你不需要一个十一个十的来拼接，可以看一下代码)

就这个十十的拼接可以就是一个十一个十的先拼接，之后多余出来的颜色格子，就用bfs添加到十的周围，但是代码确实太麻烦了

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<map>
     6 #include<math.h>
     7 using namespace std;
     8 typedef long long ll;
     9 const int maxn=1e5+5;
    10 const int mod=26;
    11 const int INF=0x3f3f3f3f;
    12 const int block=300;
    13 int cnt1=0,cnt2=0;
    14 int main()
    15 {
    16     int t;
    17     scanf("%d",&t);
    18     while(t--)
    19     {
    20         int w,b;
    21         scanf("%d%d",&b,&w);//b黑色  w白色
    22         if(max(w,b)>min(w,b)*3+1)
    23         {
    24             printf("NO\n");
    25             continue;
    26         }
    27         if(w==b)
    28         {
    29             printf("YES\n");
    30             for(int i=3; i<=w+b+2; ++i)
    31                 printf("5 %d\n",i);
    32         }
    33         else if(b<w)
    34         {
    35             printf("YES\n");
    36             w=w-b-1;//将在一行的减掉
    37             for(int i=4; i<=b*2+4; i++)
    38             {
    39                 printf("4 %d\n",i);
    40                 if(w>0 && i&1)
    41                 {
    42                     printf("3 %d\n",i);
    43                     w--;
    44                 }
    45                 if(w>0  && i&1 )
    46                 {
    47                     printf("5 %d\n",i);
    48                     w--;
    49                 }
    50             }
    51         }
    52         else if(b>w)
    53         {
    54             swap(b,w);
    55             printf("YES\n");
    56             w=w-b-1;//将在一行的减掉,再对这一行的某些部分添加格子变成十
    57             for(int i=4; i<=b*2+4; i++)
    58             {
    59                 printf("3 %d\n",i);
    60                 if(w>0 && i&1)
    61                 {
    62                     printf("2 %d\n",i);
    63                     w--;
    64                 }
    65                 if(w>0  && i&1 )
    66                 {
    67                     printf("4 %d\n",i);
    68                     w--;
    69                 }
    70             }
    71         }
    72     }
    73     return 0;
    74 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11532175.html

[Link 1]: https://codeforc.es/contest/1196/problem/E
[1633695-20190917103051936-695376743.png]: https://img2018.cnblogs.com/blog/1633695/201909/1633695-20190917103051936-695376743.png
[Link 2]: https://blog.csdn.net/sdau_fangshifeng/article/details/97238256
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif