algorithm - 计算向量中的抖动字符串

Question

PROBLEM STATEMENT

Sometimes when computer programs have a limited number of colors to use, they use a technique called dithering. Dithering is when you use a pattern made up of different colors such that when the colors are viewed together, they appear like another color. For example, you can use a checkerboard pattern of black and white pixels to achieve the illusion of gray.

You are writing a program to determine how much of the screen is covered by a certain dithered color. Given a computer screen where each pixel has a certain color, and a list of all the solid colors that make up the dithered color, return the number of pixels on the screen that are used to make up the dithered color. Each pixel will be represented by a character in screen. Each character in screen and in dithered will be an uppercase letter ('A'-'Z') representing a color.

Assume that any pixel which is a color contained in dithered is part of the dithered color.

DEFINITION

Class: ImageDithering
Method: count
Parameters: string, vector <string>
Returns: int
Method signature: int count(string dithered, vector <string> screen)

CONSTRAINTS

• dithered will contain between 2 and 26 upper case letters ('A'-'Z'), inclusive.
• There will be no repeated characters in dithered.
• screen will have between 1 and 50 elements, inclusive.
• Each element of screen will contain between 1 and 50 upper case letters ('A'-'Z'), inclusive.
• All elements of screen will contain the same number of characters.

EXAMPLES

0)

"BW"
{ "AAAAAAAA",
  "ABWBWBWA",
  "AWBWBWBA",
  "ABWBWBWA",
  "AWBWBWBA",
  "AAAAAAAA"}

Returns: 24

Here, our dithered color could consist of black (B) and white (W) pixels, composing a shade of gray. In the picture, there is a dithered gray square surrounded by another color (A).

1)

"BW"
{ "BBBBBBBB",
  "BBWBWBWB",
  "BWBWBWBB",
  "BBWBWBWB",
  "BWBWBWBB",
  "BBBBBBBB"}

Returns: 48

Here is the same picture, but with the outer color replaced with black pixels. Although in reality, the outer pixels do not form a dithered color, your algorithm should still assume they are part of the dithered pattern.

2)

"ACEGIKMOQSUWY"
{ "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
  "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
  "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
  "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
  "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
  "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX"}

Returns: 150

A picture of vertical stripes, every other stripe is considered part of the dithered color.

3)

"CA"
{"BBBBBBB",
 "BBBBBBB",
 "BBBBBBB"}

Returns: 0

The dithered color is not present.

4)

"DCBA"
{"ACBD"}

Returns: 4

The order of the colors doesn't matter.

我不明白如何计算那些向量中的抖动字符串。

与示例 0 一样，“ABWBWBWA”行从左侧开始计数为 3 个“BW”，从右侧开始计数为 2 个“BW”。应该怎么算？

Answer 1

您不计算整个字符串的实例(例如“BW”)，您计算单个字符的实例(例如“B”或“W”)。查看规范(我的重点):

Given a computer screen where each pixel has a certain color, and a list of all the solid colors that make up the dithered color, return the number of pixels on the screen that are used to make up the dithered color. Each pixel will be represented by a character in screen. Each character in screen and in dithered will be an uppercase letter ('A'-'Z') representing a color.

Assume that any pixel which is a color contained in dithered is part of the dithered color.

示例 0 在一组屏幕中有 24 个“B”和“W”字符实例；示例 1 总共有 48 个“B”或“W”字符；等等。您应该能够从示例中推断出这一点，因为示例 2 包含目标字符串“ACEGIKMOQSUWY”的零个实例，但返回值不为零。