像素填充工具这是一个有趣的难题，请帮助我" [英] pixel fill tool " its an interesting puzzle pls help me"
问题描述
拼图说明
接受代码的完整列表在《代码提交指南》中.
白天，您在一家飞速发展的设计公司工作，而到了晚上，您以 hacker 有价值的程序员的身份向互联网兜售，这些程序员倾向于为开源做贡献.没有人知道您的双重身份，同事有时会挑战您解决随机问题.
当您在午餐时间聊天时，一位同事提到他发现了大量的黑白数码照片.他问您仅通过使用图像处理程序中的像素填充工具，将所有这些照片变成白色将需要单击几下.像素填充工具是一项简洁的功能，只需单击鼠标即可将黑色像素的区域变成白色像素.
您内在的黑客 智能程序员开始思考，您确定可以以编程方式找出答案...
为了简单起见，黑白图像是由X * Y值组成的矩阵.
0代表黑色像素，而1代表白色像素.
以下是一个具有一些白色和一些黑色像素的7x5图像:
10001
10100
00000
00000
00111
00100
00100
只需单击一下，像素填充工具就会将每个黑色像素变成白色像素，直到从上一个像素无法到达黑色像素为止.一个像素通过多达八种方式与另一个像素相连:北，南，东，西和四个对角线.
只需单击两次，即可用白色像素填充上面的图像:第一次单击:
11111
11111
11111
11111
11111
11100
11100
第二次点击:
11111
11111
11111
11111
11111
11111
11111
Puzzle Description
A complete list of accepted languages is in the Code Submission Guidelines.
During the day you work at a high flying design company, but at night you troll the internet as a hacker valuable programmer that tends to contribute to open source. No one knows your dual identity and once in a while a coworker will challenge you to solve a random problem.
As you chat at lunch, a coworker mentions he found a large number of digital black and white photos. He asks you how many clicks it would take to turn all these photos white by only using the pixel fill tool in your image manipulation program. The pixel fill tool is a neat feature that turns an area of black pixels into white pixels with just the click of a mouse.
The hacker in you smart programmer you are inside starts to think, and you determine you can programmatically figure out the answer...
For the sake of simplicity, a black and white image is a matrix composed of X * Y values.
A 0 represents a black pixel and a 1 represents a white pixel.
The following is a 7x5 image with some white and some black pixels:
10001
10100
00000
00000
00111
00100
00100
With one click, the pixel fill tool turns each black pixel into a white one until there isn''t a black pixel that can be reached from the previous pixel. A pixel is connected with another one in up to eight ways: north, south, east, west and the four diagonals.
The image above can be filled with whites pixel with just two clicks: First click:
11111
11111
11111
11111
11111
11100
11100
Second click:
11111
11111
11111
11111
11111
11111
11111
推荐答案
MINESWEEPER！
我喜欢这个任务.
掌握了一些代码后，请深入了解我们.
并向我们提供您的解决方案，我们不做作业.您可以提出具体问题，我们很乐意为您提供帮助，但是我们不提供任何形式的代码(...因为我们需要为此付费).
MINESWEEPER!
I love this quest.
Give us a sneak into your code when you''ve got some.
And present us your solution, we do not do homework. You can ask specific questions and we are delighted to help you, but we do not provide code in any form (...as we would have to be paid for that).
这是这是一个非常无聊的问题，因为没有任何策略:一种算法在理解了问题之后就显而易见.您只需要选择第一个零，然后按照规则实际执行洪水填充，并重复进行直到所有零都消失为止.计算这样的循环数.
您真的希望有人会比我在解决这个无聊的问题时志愿提供的帮助更多吗?因为这个问题被标记为家庭作业"，所以您应该会一直玩得很开心.学校为您提供学习的机会，善用它.一些经验永远不会伤害.现在，该上班了！
祝你好运，
—SA
This is a very boring problem, because there is no any strategy: an algorithm is apparent right after one understands the problem. You just need to pick first zero, actually perform flood fill following the rules and repeat until all zeros are gone. Count the number of such cycles.
Do you really hope that someone will volunteer to help you more than I just did with such a boring problem? As this question is marked "homework", you''re supposed to have all this fun along. School gives you a chance to learn something, use it well. Some experience will never hurt. Now, time to get to work!
Good luck,
—SA
我在这里想到了两种策略:
1个不同的零区域计数
零区域是8位连接的零的区域.它的边界是8路连接的一个区域或图像边界.
您需要的点击次数是未相互连接的零区域的数量.
对于其他图像，另一种策略可能会更快:
2个多次反转
您可以通过重复填充中间像素，黑白交替来获得所有黑色像素.
您需要的点击次数是黑白像素相互填充的最高层数".
I think of two strategies here:
1 distinct zero-regions count
A zero-region is a region of 8-way connected zeros. Its border is an 8-way connected one-region or the image border.
The number of clicks you need is the number of zero-regions that are not connected to each other.
For other images, another strategy could be faster:
2 multiple inversions
You can get all the black pixels by repeatedly pixel fill the middle pixel, black and white alternating.
The number of clicks you need is the highest number of "layers" that black and white pixels are stuffed into one another.
0010000100
1110000111
0000000000
0000000000
1110000111
0010000100在这里，您首先要对中间像素进行白色处理，然后留下四个黑角.黑色居中，产生完全黑色的图像.最后又变白了.
与使用第一种策略所需的5次运行相比，这将进行3次运行.
同时处理并采取更快的处理方法.
哦，我可以想到组合起来最快的星座.
Here, you would first white the middle pixel, leaving four black corners. The black the middle, resulting in a completely black image. And finally white again.
That would be 3 runs compared to the 5 that would be necessary using the first strategy.
Process both and take the faster one.
Oh, and I can think of constellations where a combination would be fastest.
这篇关于像素填充工具这是一个有趣的难题，请帮助我"的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
