cometoj---contest#3 棋盘

2019/05/13 21:14
阅读数 10

棋盘:(状压dp)

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

题目描述

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

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

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

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

 

输入描述

第一行有一个正整数 N (1N105)。

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

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

 

输出描述

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

 

 

样例输入 1 

 

3
1 0 0
0 0 1

 

样例输出 1

 

2

样例输入 2 

5
0 1 0 1 0
0 0 1 0 0

样例输出 2

1

提示

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

样例二中可以将位置 (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代码:
 1 /* */
 2 # include <stdio.h>
 3 int main()
 4 {
 5     long long int map[2][110000]={0}, n, i, j, sum=0;
 6     scanf("%lld", &n);
 7     for( i=0; i<2; i++ )
 8     {
 9         for( j=0; j<n; j++ )
10         {
11             scanf("%lld", &map[i][j]);
12         }
13     }
14     int nowone = 0;
15     int nowtwo = 0;
16     int flag=0;
17     int f;
18     int pre;
19     for( j=0; j<n; j++ )
20     {
21         nowone=0;
22         nowtwo=0;
23         if( map[0][j] )
24         {
25             nowone = 1;
26         }
27         if( map[1][j] )
28         {
29             nowtwo = 1;
30         }
31         if( nowone || nowtwo )
32         {
33             if( flag==0 )
34             {
35                 f = j;
36                 if( nowone )///上1下0
37                 {
38                     pre = 1;
39                 }
40                 if( nowtwo )///上0下1
41                 {
42                     pre = 2;
43                 }
44                 if( nowone && nowtwo )///上1下1
45                 {
46                     pre = 3;
47                 }
48                 flag = 1;
49             }
50             else
51             {
52                 if( nowone && nowtwo )
53                 {
54                     sum += j - f - 1;
55                     pre = 3;
56                 }
57                 if( nowone && !nowtwo )///上1下0
58                 {
59                     sum += j-f-1;
60                     if( pre==2 )///上0下1
61                     {
62                         sum++;
63                         pre = 3;///前方不连通则变为联通,此时这一列的状态变为上1下1
64                     }
65                     else
66                     {
67                         pre = 1;///前方已经联通,这一列的状态不变
68                     }
69                 }
70                 if( !nowone && nowtwo )///上0下1
71                 {
72                     sum += j - f - 1;
73                     if( pre==1 )///上1下0
74                     {
75                         sum++;
76                         pre = 3;///前方不连通则变为联通,此时这一列的状态变为上1下1
77                     }
78                     else
79                     {
80                         pre=2;///前方已经联通,这一列的状态不变
81                     }
82                 }
83                 f = j;
84             }
85         }
86     }
87     printf("%lld\n", sum);
88     return 0;
89 }
View Code

 

 
 
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部