2013-10-22-FloodFill.md

FloodFill simple implementation
----

Oct. 22, 2013 看见someone提到Flood fill algorithm, 惭愧，不熟悉这个名字，于是Google一下，竟然跟BFS很像，于是想着要简单实现一下。一直拖，拖到了昨晚, Sunday, Nov. 4, 才弄出个结果。

下面这图是在Windows > Paint软件中画的，一个奇怪的形状，假如用Paint软件中的fill工具可以把这个奇怪的形状填满某一种颜色。那假如手工实现，怎么搞呢?

下面是结果，分别是填了10000次，20000次...的结果。

 

 

从程序的结果来看，在一定次数之后就填满了整个奇怪的形状。如上面的结果中，从10000次到20000次扩展的区域是否跟从20000到30000次拓展的区域一样大呢，跟什么有关？(After some steps, the shape will be filled. From the result images aboved, the extended red region added during from 10000 to 20000 is the same as the region added during from 20000 to 30000? what is the reason behind that.)

New functions learned:
std::stoi, std::to_string functions.

Source code: https://github.com/renc/FloodFill 

weekly update - one list for two item types

这一周都在为之前的设计错误埋单。一个(two dimension) double linked list在当前代码中被广泛使用，其中的ListNode被当作是一种类A了，现在新需求是加入另一种新的种类B，但是要求是用户看到的A跟B是可以混排的，例如A->A->B->A->B->B->A-....。之前为了不影响已有的code，不改当前的list，而重新加入一个新的list，维护那些B，两天时间尝试给这新的ListB来添加维护ListNodeB的功能，例如add / remove/ insert / move等。当作到undo的时候，不行，ListB的操作需要考虑list中前后nodes类型，上下文，A还是B呢？太烦。
于是转肽，把旧的ListNode扩展为默认是typeA, 额外要求的话可以是typeB，于是A and B这两种类型的东西可以mix到一个list里面，因为A and B are objects of the same ListNode。但旧代码对这个list的操作，例如traverse the list to visit every ListNode, 都是把ListNode做为A的，现在要添加判断了：假如是A，照旧，假如是B，新的做法。等于做surgery，但是觉得应该坚持觉得对的而不是避开繁琐的。

这是最简单实例 (one dimention double linked list):
struct ListNode {
  ListNode *m_pPrve, m_pNext;
  bool m_bTypeA; // default is true;
  ...
};
class List {
  ListNode m_pHead;
};