Flood Fill Algorithm

Flood Fill Algorithm

We might have encountered this at many places. Paint tool is one such example, when we say fill with color in paint, it fills the neighboring areas with the same color.
For examples in the below image when we do a fill color on the white area, we would want all the neighboring white areas to be colored.

The algorithm is very simple. We start with the user selected grid, fill it with color and then check the top, bottom, right and left grid and fill them as well. We do this recursively to achieve the end result.

Below is the procedure

floodFill(vector<vector<int>grid>, x, y, oldColor, newColor)

• If x or y is outside the grid, then return.
• If color of grid[x][y] is not same as oldColor, then return
• do the same for top, down, right and left.

    floodFillUtil(grid, x+1, y, oldColor, newColor);
    floodFillUtil(grid, x-1, y, oldColor, newColor);
    floodFillUtil(grid, x, y+1, oldColor, newColor);
    floodFillUtil(grid, x, y-1, oldColor, newColor); 

Lets see a C++ implementation for this algorithm

Multithreading:6.Print odd and even numbers using two threads

In this program we are going to look into how to print odd numbers using one thread and even numbers using another thread, the numbers have to be printed in order.
In the below code we have added two methods one to print odd numbers and the other to print even numbers, we call one from t1 and another from t2.

Multithreading:5.condition_variable

Many a times we would want a thread to execute some commands based on some conditions. For this we are going to use std:: condition_variable. This class methods such wait, notify which would either make a thread wait or notify other threads. That is exactly the functionality we would need.

To go into code, we would want to understand to basic methods in the class std::condition_variable. One is wait and the other is notify

Wait 
void wait( std::unique_lock<std::mutex>& lock );
lock:an object of type std::unique_lock<std::mutex>, which must be locked by the current thread. Need not be locked till notify

template< class Predicate >
void wait( std::unique_lock<std::mutex>& lock, Predicate pred );
Pred: predicate which returns ​false if the waiting should be continued.

Notify
void notify_all() noexcept;
Unblocks all threads currently waiting for *this.

In the below code we want the main thread to print abcdef and the thread t1 to print 123456.
For this to happen, we want the main thread to start printing the alphabets and t1 to wait till the main completes its job. And we need some variable to tell that the main is done with this job, in this case we are using a bool alphadone.

Multithreading:4.Deadlock

Suppose we want to protect our resource doubly and we introduce two mutex to guard the resource.
Here in the below code we are locking m1 first in thread t1 and m2 first in thread t2. Now to lock m2 in thread t1 it will be waiting for t2 to unlock, which never happens. That is a deadlock situation.

To avoid this situation

• Prefer locking single mutex at a time 
• Avoid locking a mutex and then calling a user provided function, because the user provided function might crash and we may never be able to unlock it. 
• Use std::lock() to lock more than one mutex. 
• Lock the mutex in same order.

Multithreading: 3.Mutex

When we execute the below code. The output would appear random. We are trying to print 1 to 9 from main and 10 to 19 from the thread.

The output looks like below

threadMain101
threadMain112
threadMain123
threadMain134
threadMain145
threadMain156
threadMain167
threadMain178
threadMain189
thread19

The output looks haphazard and not understandable. This is because both the main thread and the thread t are fighting for the common resource cout. We have to make a change in our code to control the access of cout. meaning if one thread is accessing cout, other thread has to simply wait for access.
We use std::mutex lock and unlock methods to do that.

below is the output after using mutex

thread:10
thread:11
thread:12
thread:13
thread:14
thread:15
thread:16
thread:17
thread:18
thread:19
Main:1
Main:2
Main:3
Main:4
Main:5
Main:6
Main:7
Main:8
Main:9

Multithreading: 2.Join and Joinable

Most of the times the main thread may execute in a shorter period of time than the child threads.
If the main thread completes before the child thread, then the child thread will be orphaned.
The main thread needs to wait for the child thread to complete.
We need to call t1.join() on the thread instance to make the main thread wait till t1 execution is complete.


Also we need to check if a thread is joinable (thread with active code of execution), before calling join.

Multithreading :1.Create thread

We will be using std::thread class to create threads.
std:thread is introduced in C++11.
We can start creating threads by including the thread header file. To create a thread, we need to pass the code that needs to be executed in the constructor of the thread.
As soon as the thread object is created, a new thread is launched, which will execute the code passed to the constructor.


The constructor takes

• a function object
• a function pointer
• a  lambda expression