Filling a bounded region, Turbo C

A program to fill a bounded region to be implemented in Turbo C, as a practical of Computer Graphics. As input, a point inside the bounded region is given. 


Implementation:
Starting from the given point apply dfs to the points at n,s,e and w.  As the base conditions check whether the color at the given pixel is equal to the boundary. If it is, return. Also even if it is equal to the fill color, return. Sadly I had to program in Turbo C, yes our college still uses that compiler. Here 4 is the fill color.


Function:
// x and y coordinates of point inside
// getmaxcolor() is the color of boundary
// fill the pixel with color 4


dfs(int x, int y) { 
  if (getpixel(x,y)==getmaxcolor() || getpixel(x,y)==4)
      return; 
  putpixel(x,y,4); 
  dfs(x-1,y);
  dfs(x+1,y);
  dfs(x,y-1);
  dfs(x,y+1); 
}



Floodfill implementation using dfs (stack)
Image Source: Wikipedia 


The output is pretty interesting when you use a delay function with it.    

929 - Number Maze Uva Online Judge

Tried the problem in Java, completed it. But in Java it is too slow that is why unable to submit it. Solved it using BFS with PriorityQueue.

929 - Number Maze

Time limit

Java

3.000

0.144

8 hours ago

Programming in 61 minutes

Check out this great link by Dhruv Matani http://dhruvbird.com/61.html

PriorityQueue Implementation

While learning Dijkstra's I have come across this class PriorityQueue.

class PriorityQueue

It basically keeps the elemts sorted accordingly. The head of the queue is the least element to the specified ordering. Implementation note: this implementation provides O(log(n)) time for the insertion methods (offer, poll, remove() and add) methods; linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

How will the sorting be done?

This is either naturally specified or otherwise, that depends on the arguments of the constructor. Like if the class Integer is specified then the comparison will be done using the compareTo method of the comparable interface. This is when we do 

PriorityQueue temp = new PriorityQueue();

For adding and removal the methods which are available are : add() and poll() (removes the element from the head of the Queue)

Program

public static void main(String[] args) {

PriorityQueue temp = new PriorityQueue();

temp.add(4); temp.add(2); temp.add(3); temp.add(7); temp.add(1);

while (!temp.isEmpty()) {

System.out.println(temp.poll());

}

}

Output

1

2

3

4

7

This being the case when we use a class which has already implemented the Comparable Interface. 

Now suppose that we have user defined objects to be stored in the PriorityQueue, then for the sorting to be done the user defined class will implement the interface Comparable and override the compareTo(Object c) method.

import java.util.PriorityQueue;

class Node implements Comparable{

public int a,b,c;

public void setA(int a) {

this.a = a;

}

public void setB(int b) {

this.b = b;

}

public void setC(int c) {

this.c = c;

}

public int compareTo(Node o) {

return new Integer(this.c).compareTo(o.c);

};

}

public class PQExample {

public static void main(String[] args) {

Node n = new Node();

n.setA(1);

n.setC(4);

Node n2 = new Node();

n2.setA(2);

n2.setC(6);

Node n3 = new Node();

n3.setA(3);

n3.setC(1);

PriorityQueue temp = new PriorityQueue();

temp.add(n); temp.add(n2);temp.add(n3);

while (!temp.isEmpty()) {

System.out.println(temp.poll().a);

}

}

}

Output

3

1

2

I learnt these concepts from Pratik Tandel (pt1989) ,  http://problemclassifier.appspot.com/