Squirrels have fuzzy tails.

0 Members and 1 Guest are viewing this topic.

Huge props for the first person who can name that algorithm.

I did some searching on the web and i suppose he uses flooding algorithm

An n by m grid has some cells filled in and others blank, in no particular pattern. Write a method to find the size of the largest block of filled cells in the grid. A block is a group of contiguous cells that share an adjacent edge. Cells in a block have north-south or east-west adjacency; diagonal adjacency does not count.

import java.awt.Point;import java.util.HashSet;import java.util.SortedSet;import java.util.PriorityQueue;import java.util.TreeSet;public class BlockProblem { private boolean [][] map; //true is full, false is empty private PriorityQueue<Block> solidblocks; private int n; //analgous to x private int m; //analgous to y private boolean blocksarefound; public BlockProblem() { n = 50; m = 50; map = new boolean[n][m]; solidblocks = new PriorityQueue<Block>(); blocksarefound=false; } public BlockProblem(int newN, int newM) { n = newN; m = newM; map = new boolean [n][m]; solidblocks = new PriorityQueue<Block>(); blocksarefound=false; } public BlockProblem(boolean newmap[][], int newN, int newM) { n = newN; m = newM; map = newmap.clone(); solidblocks = new PriorityQueue<Block>(); findBlocks(); } public void setCell(int x, int y, boolean value) { blocksarefound=false; map[x][y]= value; } public void findBlocks() { HashSet<Point> visitedcells= new HashSet<Point>(n*m); Point tempPoint = new Point(0,0); for (int x=0; x<n; x++)//the x { for (int y=0; y<m; y++)//the y { tempPoint.setLocation(x, y); if(!visitedcells.contains(tempPoint)) { if (map[tempPoint.x][tempPoint.y]) solidblocks.add(new Block (map, n, m, visitedcells, tempPoint)); else visitedcells.add(tempPoint); } } } blocksarefound=true; } public Block biggest() { if (!blocksarefound) { findBlocks(); } return solidblocks.peek(); } public String toString() { String outputString= "The Block Problem \n"; //the order in which we put out here is swaped //so it coorisponds with a more traditional sense //of x and y....cartesian like. for (int y= m-1; y >=0; y--)//the y { for (int x=0; x<n; x++)//the x { if (map[x][y]) outputString += "X"; else outputString += "O"; } outputString += "\n"; } outputString += "\nThe Blocks are\n"; for (Block b : solidblocks) { outputString += b; outputString += "\n"; } outputString += "The largest Block is \n"; outputString += solidblocks.peek(); return outputString; }}

import java.util.LinkedList;import java.util.Queue;import java.awt.Point;import java.util.HashSet;public class Block implements Comparable { private LinkedList<Point> members; private int size; public Block() { members = new LinkedList<Point>(); size = 0; } public Block(boolean [][]map, int n, int m, HashSet<Point> visited, Point start) { members = new LinkedList<Point>(); size = floodFillIterative(map, n, m, visited, start); } public int floodFillIterative(boolean [][]map, int n, int m, HashSet<Point> visited, Point start) { System.out.println("starting on "+start); int count=0; Queue<Point> toCheck; toCheck = new LinkedList<Point>(); Point current = new Point(start); //push the current Point onto the queue toCheck.offer(current); while (toCheck.size()!= 0) { current = toCheck.poll(); System.out.println("\tpopped "+ current); //have we been here? (base case for the recursion) if (visited.contains(current)) { //yes so this doesn't count System.out.println("\tHas already been visited"); continue; } else { //we have not been here so we add it to the visited hash set visited.add(current); //add it to the list of memebers in this block count++; members.add(current); //add cell to the north to the queue if possible if ((current.y+1) < m) { if (map[current.x][current.y+1]) { toCheck.offer(new Point(current.x, current.y+1)); System.out.println("\tpushed "+current.x+" "+(current.y+1)); } } //add cell to the south to the queue if possible if ((current.y-1) >= 0) { if (map[current.x][current.y-1]) { toCheck.offer(new Point(current.x, current.y-1)); System.out.println("\tpushed "+current.x+" "+(current.y-1)); } } //add cell to the east to the queue if possible if ((current.x+1) < n) { if (map[current.x+1][current.y]) { toCheck.offer(new Point(current.x+1, current.y)); System.out.println("\tpushed "+(current.x+1)+" "+current.y); } } //add cell to the west to the queue if possible if ((current.x-1) >= 0) { if (map[current.x-1][current.y]) { toCheck.offer(new Point(current.x-1, current.y)); System.out.println("\tpushed "+(current.x-1)+" "+current.y); } } } System.out.println(); } System.out.println(); return count; } public int getSize() { return size; } public LinkedList<Point> getMembers() { return members; } public int compareTo(Object other) { Block otherBlock = (Block) other; if(this.size<otherBlock.size)return 1; if(this.size==otherBlock.size)return 0; return -1; } public String toString() { String outputString="Size of Block is"; outputString += " "+size; outputString += "\nmembers:\n"; for (Point p: members) { outputString += p; outputString += "\n"; } return outputString; }}