cometoj---contest#3 棋盘

棋盘：（状压dp）

传送门：https://www.cometoj.com/contest/38/problem/B?problem_id=1535

题目描述

小猫有一个 2×N 的棋盘，每一个格子放着一个黑棋子或白棋子。

小熊觉得小猫的棋盘不够好看，想要把棋盘上的一部分白棋子替换成黑棋子，使得所有黑棋子都能够在仅允许上下左右四个方向走，且仅经过黑棋子在的格子的情况下两两互相到达。

小熊想知道至少要将多少个白棋子替换成黑棋子。

注意：不能将黑棋子替换成白棋子。

输入描述

第一行有一个正整数 N (1≤N≤10⁵)。

接下来两行，每行 N个整数，描述整个棋盘。若第 i 行的第 j个整数是 0，代表棋盘 (i,j) 的位置放着白棋子，若是 1 则放着黑棋子。

数据保证至少存在一个黑棋子。

输出描述

输出一行包含一个整数，表示答案。

样例输入 1

样例输出 1

样例输入 2

样例输出 2

提示

样例一中可以将第一行的两个白棋子替换成黑棋子。

样例二中可以将位置 (1, 3)(1,3) 的白棋子换成黑棋子。

大佬分析：（自己完全没想到QAQ）

题⽬意思就是说通过把0 变成1 来将所有变成⼀个联通块，要求最少的变换个数。我是⽤的暴⼒模拟，从第⼀列
开始遍历每⼀列，因为只有两⾏，含1的每⼀列⽆⾮就是：上 1下 1，上0 下 1，上1 下0 ；只有这三种情况是需要变
化前⾯列的来使联通的，观察这三种情况，上1 下1 时，变换个数就是上⼀次有的列号与当前列号差值的绝对
值 (直接由上⼀个有的位置沿着⾏直线变化到当前列)；上 1下0 时，就需要看上⼀次有1 的那⼀列的1 的情况
了，如果上⼀次有 1处和当前列有1 处是同⼀⾏，说明可以直线变换过来，变换个数就是上⼀次有 1的列号与当前
列号差值的绝对值-1 ，如果不是同⼀⾏，则需要多加 1（需要多变换⼀个棋⼦）；上下的情况和上⼀种情况类
似解法。因此关键就是保存上⼀次有 1处的那列情况，在遇到某列有时考虑上⾯的情况然后累加就⾏了。

AC代码：

 /* */

 # include <stdio.h>

 int main()

 {

     long long int map[][]={}, n, i, j, sum=;

     scanf("%lld", &n);

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

     {

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

         {

             scanf("%lld", &map[i][j]);

         }

     }

     int nowone = ;

     int nowtwo = ;

     int flag=;

     int f;

     int pre;

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

     {

         nowone=;

         nowtwo=;

         if( map[][j] )

         {

             nowone = ;

         }

         if( map[][j] )

         {

             nowtwo = ;

         }

         if( nowone || nowtwo )

         {

             if( flag== )

             {

                 f = j;

                 if( nowone )///上1下0

                 {

                     pre = ;

                 }

                 if( nowtwo )///上0下1

                 {

                     pre = ;

                 }

                 if( nowone && nowtwo )///上1下1

                 {

                     pre = ;

                 }

                 flag = ;

             }

             else

             {

                 if( nowone && nowtwo )

                 {

                     sum += j - f - ;

                     pre = ;

                 }

                 if( nowone && !nowtwo )///上1下0

                 {

                     sum += j-f-;

                     if( pre== )///上0下1

                     {

                         sum++;

                         pre = ;///前方不连通则变为联通，此时这一列的状态变为上1下1

                     }

                     else

                     {

                         pre = ;///前方已经联通，这一列的状态不变

                     }

                 }

                 if( !nowone && nowtwo )///上0下1

                 {

                     sum += j - f - ;

                     if( pre== )///上1下0

                     {

                         sum++;

                         pre = ;///前方不连通则变为联通，此时这一列的状态变为上1下1

                     }

                     else

                     {

                         pre=;///前方已经联通，这一列的状态不变

                     }

                 }

                 f = j;

             }

         }

     }

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

     return ;

 }

巴特西

cometoj---contest#3 棋盘

最新文章

热门文章