CF991D.Bishwock

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Bishwock is a chess figure that consists of three squares resembling an "L-bar". This figure can be rotated by 90, 180 and 270 degrees so it can have four possible states:

XX XX .X X.
X. .X XX XX

Bishwocks don't attack any squares and can even occupy on the adjacent squares as long as they don't occupy the same square.

Vasya has a board with 2×n2\times n squares onto which he wants to put some bishwocks. To his dismay, several squares on this board are already occupied by pawns and Vasya can't put bishwocks there. However, pawns also don't attack bishwocks and they can occupy adjacent squares peacefully.

Knowing the positions of pawns on the board, help Vasya to determine the maximum amount of bishwocks he can put onto the board so that they wouldn't occupy the same squares and wouldn't occupy squares with pawns.

Bishwock 是一种由三个方格组成的国际象棋棋子,形状类似一个“L 形杆”。该棋子可绕中心旋转 90°、180° 和 270°,因此共有四种可能的朝向:

XX XX .X X.
X. .X XX XX

Bishwock 不攻击任何方格,且彼此之间甚至可以放置在相邻方格上,只要不占据同一方格即可。

瓦夏有一块 2×n2\times n 的棋盘,他希望在上面放置若干 Bishwock。然而令他沮丧的是,棋盘上已有若干方格被兵(pawn)占据,而瓦夏无法在这些位置放置 Bishwock。不过,兵也不攻击 Bishwock,且兵与 Bishwock 可以和平共存于相邻方格。

已知棋盘上兵的位置,请帮助瓦夏确定:在不重叠、且不覆盖任何兵所在方格的前提下,最多能在棋盘上放置多少个 Bishwock。

输入格式

The input contains two nonempty strings that describe Vasya's board. Those strings contain only symbols "0" (zero) that denote the empty squares and symbols "X" (uppercase English letter) that denote the squares occupied by pawns. Strings are nonempty and are of the same length that does not exceed 100100.

输入包含两个非空字符串,用于描述瓦西娅的棋盘。这些字符串仅包含字符 "0"(数字零),表示空格;以及字符 "X"(大写英文字母),表示被兵占据的格子。字符串非空,且长度相等,长度不超过 100100。

输出格式

Output a single integer — the maximum amount of bishwocks that can be placed onto the given board.

输出一个整数——即可以放置在给定棋盘上的bishwock的最大数量。

输入输出样例

  • 输入#1

    00
    00

    输出#1

    1
  • 输入#2

    00X00X0XXX0
    0XXX0X00X00

    输出#2

    4
  • 输入#3

    0X0X0
    0X0X0

    输出#3

    0
  • 输入#4

    0XXX0
    00000

    输出#4

    2

输入解题思路,AI测评打分。不知道怎么写?

首页