Detecting edges is a common image processing problem. For example, digital cameras often feature face detection. Some robotic competitions require the robots to find a ball using a digital camera, so the robot needs to be able to “see” a ball.
One way to look for an edge in a picture is to compare the color at the current pixel with the pixel in the next column to the right. If the colors differ by more than some specified amount, this indicates that an edge has been detected and the current pixel color should be set to black. Otherwise, the current pixel is not part of an edge and its color should be set to white (Figure 12). How do you calculate the difference between two colors?
public void edgeDetection(int edgeDist)
{
Pixel leftPixel = null;
Pixel rightPixel = null;
Pixel[][] pixels = this.getPixels2D();
Color rightColor = null;
for (int row = 0; row < pixels.length; row++)
{
for (int col = 0; col < pixels[0].length-1; col++)
{
leftPixel = pixels[row][col];
rightPixel = pixels[row][col+1];
rightColor = rightPixel.getColor();
if (leftPixel.colorDistance(rightColor) > edgeDist)
leftPixel.setColor(Color.BLACK);
else
leftPixel.setColor(Color.WHITE);
}
}
}
Classwork:
Exercises
1. Notice that the current edge detection method works best when there are big color changes from left to right but not when the changes are from top to bottom. Add another loop that compares the current pixel with the one below and sets the current pixel color to black as well when the color distance is greater than the specified edge distance.
2. Work in groups to come up with another algorithm for edge detection.
How image processing is related to new scientific breakthroughs
Many of today’s important scientific breakthroughs are being made by large, interdisciplinary collaborations of scientists working in geographically widely distributed locations, producing, collecting, and analyzing vast and complex datasets.
One of the computer scientists who works on a large interdisciplinary scientific team is Dr. Cecilia Aragon. She is an associate professor in the Department of Human Centered Design & Engineering and the eScience Institute at the University of Washington, where she directs the Scientific Collaboration and Creativity Lab. Previously, she was a computer scientist in the Computational Research Division at Lawrence Berkeley National Laboratory for six years, after earning her Ph.D. in Computer Science from UC Berkeley in 2004. She earned her B.S. in mathematics from the California Institute of Technology.
Her current research focuses on human-computer interaction (HCI) and computer-supported cooperative work (CSCW) in scientific collaborations, distributed creativity, information visualization, and the visual understanding of very large data sets. She is interested in how social media and new methods of computer-mediated communication are changing scientific practice. She has developed novel visual interfaces for collaborative exploration of very large scientific data sets, and has authored or co-authored many papers in the areas of computer-supported cooperative work, human-computer interaction, visualization, visual analytics, image processing, machine learning, cyberinfrastructure, and astrophysics.
In 2008, she received the Presidential Early Career Award for Scientists and Engineers (PECASE) for her work in collaborative data-intensive science. Her research has been recognized with four Best Paper awards since 2004, and she was named one of the Top 25 Women of 2009 by Hispanic Business Magazine. She was the architect of the Sunfall data visualization and workflow management system for the Nearby Supernova Factory, which helped advance the study of supernovae in order to reduce the statistical uncertainties on key cosmological parameters that categorize dark energy, one of the grand challenges in physics today.
Cecilia Aragon is also one of the most skilled aerobatic pilots flying today. A two-time member of the U.S. Aerobatic Team, she was a medalist at the 1993 U.S. National Championships and the 1994 World Aerobatic Championships, and was the California State Aerobatic Champion.
Classwork:
Activity 7: A7: Mirroring part of a picture
public void mirrorTemple()
{
int mirrorPoint = 276;
Pixel leftPixel = null;
Pixel rightPixel = null;
int count = 0;
Pixel[][] pixels = this.getPixels2D();
// loop through the rows
for (int row = 27; row < 97; row++)
{
// loop from 13 to just before the mirror point
for (int col = 13; col < mirrorPoint; col++)
{
leftPixel = pixels[row][col];
rightPixel = pixels[row][mirrorPoint - col + mirrorPoint];
rightPixel.setColor(leftPixel.getColor());
}
}
}
Questions
1. How many times would the body of this nested for loop execute?
for (int row = 7; row < 17; row++)
for (int col = 6; col < 15; col++)
2. How many times would the body of this nested for loop execute?
for (int row = 5; row <= 11; row++)
for (int col = 3; col <= 18; col++)
Exercises
1. Check the calculation of the number of times the body of the nested loop executes by adding an integer count variable to the mirrorTemple method that starts out at 0 and increments inside the body of the loop. Print the value of count after the nested loop ends.
2. Write the method mirrorArms to mirror the arms on the snowman (“snowman.jpg”) to make a snowman with 4 arms. Write a class (static) test method in PictureTester to test this new method and call it in the main method.
3. Write the method mirrorGull to mirror the seagull (“seagull.jpg”) to the right so that there are two seagulls on the beach near each other. Write a class (static) test method in PictureTester to test this new method and call it in the main method.
public void createCollage()
{
Picture flower1 = new Picture("flower1.jpg");
Picture flower2 = new Picture("flower2.jpg");
this.copy(flower1,0,0);
this.copy(flower2,100,0);
this.copy(flower1,200,0);
Picture flowerNoBlue = new Picture(flower2);
flowerNoBlue.zeroBlue();
this.copy(flowerNoBlue,300,0);
this.copy(flower1,400,0);
this.copy(flower2,500,0);
this.mirrorVertical();
this.write("collage.jpg");
}
Exercises
1. Create a second copy method that adds parameters to allow you to copy just part of the fromPic. You will need to add parameters that specify the start row, end row, start column, and end column to copy from. Write a class (static) test method in PictureTester to test this new method and call it in the main method.

2. Create a myCollage method that has at least three pictures (can be the same picture) copied three times with three different picture manipulations and at least one mirroring. Write a class (static) test method in PictureTester to test this new method and call it in the main method.
Classwork:
1. Open Picture.java and look for the method getPixels2D. Is it there?
2. Open SimplePicture.java and look for the method getPixels2D. Is it there?
3. Does the following code compile?
DigitalPicture p = new DigitalPicture();
4. Assuming that a no-argument constructor exists for SimplePicture, would the following
code compile?
DigitalPicture p = new SimplePicture();
5. Assuming that a no-argument constructor exists for Picture, does the following code
compile?
DigitalPicture p = new Picture();
6. Assuming that a no-argument constructor exists for Picture, does the following code
compile?
SimplePicture p = new Picture();
7. Assuming that a no-argument constructor exists for SimplePicture, does the following
code compile?
Picture p = new SimplePicture();
More Questions:
List nameList = new ArrayList();
Why wouldn’t you just declare nameList to be of the type ArrayList?
What do you think you will see if you modify the beach picture in the images folder to set all the blue values to zero?
Do you think you will still see a beach?
Exercises
1. Open PictureTester.java and run its main method. You should get the same results as running the main method in the Picture class. The PictureTester class contains class (static) methods for testing the methods that are in the Picture class.
2. Uncomment the appropriate test method in the main method of PictureTester to test any of the other methods in Picture.java. You can comment out the tests you don’t want to run. You can also add new test methods to PictureTester to test any methods you create in the Picture class.
Homework:
Exercises
3. Using the zeroBlue method as a starting point, write the method keepOnlyBlue that will keep only the blue values, that is, it will set the red and green values to zero. Create a class (static) method to test this new method in the class PictureTester. Be sure to call the new test method in the main method in PictureTester.
4. Write the negate method to negate all the pixels in a picture. To negate a picture, set the red value to 255 minus the current red value, the green value to 255 minus the current green value and the blue value to 255 minus the current blue value. Create a class (static) method to test this new method in the class PictureTester. Be sure to call the new test method in the main method in PictureTester.
5. Write the grayscale method to turn the picture into shades of gray. Set the red, green, and blue values to the average of the current red, green, and blue values (add all three values and divide by 3). Create a class (static) method to test this new method in the class PictureTester. Be sure to call the new test method in the main method in PictureTester.
6. Challenge — Explore the “water.jpg” picture in the images folder. Write a method fixUnderwater() to modify the pixel colors to make the fish easier to see. Create a class (static) method to test this new method in the class PictureTester. Be sure to call the new test method in the main method in PictureTester.
Write a getCount method in the IntArrayWorker class that returns the count of the number of times a passed integer value is found in the matrix. There is already a method to test this in IntArrayWorkerTester. Just uncomment the method testGetCount() and the call to it in the main method of IntArrayWorkerTester.
Write a getLargest method in the IntArrayWorker class that returns the largest value in the matrix. There is already a method to test this in IntArrayWorkerTester. Just uncomment the method testGetLargest() and the call to it in the main method of IntArrayWorkerTester.
Write a getColTotal method in the IntArrayWorker class that returns the total of all integers in a specified column. There is already a method to test this in IntArrayWorkerTester. Just uncomment the method testGetColTotal() and the call to it in the main method of IntArrayWorkerTester.
What is the row index for the top left corner of the picture?
What is the column index for the top left corner of the picture?
The width of this picture is 640. What is the right most column index?
The height of this picture is 480. What is the bottom most row index?
Does the row index increase from left to right or top to bottom?
Does the column index increase from left to right or top to bottom?
Set the zoom to 500%. Can you see squares of color? This is called pixelation. Pixelation means displaying a picture so magnified that the individual pixels look like small squares.
Homework: Picture Lab Activity 3
Exercises
Modify the main method in the PictureExplorer class to create and explore a different picture from the images folder.
Add a picture to the images folder and then create and explore that picture in the main method. If the picture is very large (for instance, one from a digital camera), you can scale it using the scale method in the Picture class.
For example, you can make a new picture (“smallMyPicture.jpg” in the images folder) one-fourth the size of the original (“myPicture.jpg”) using:
Picture p = new Picture("myPicture.jpg");
Picture smallP = p.scale(0.25,0.25);
smallP.write("smallMyPicture.jpg");
Questions
1. How many bits does it take to represent the values from 0 to 255?
2. How many bytes does it take to represent a color in the RBG color model?
3. How many pixels are in a picture that is 640 pixels wide and 480 pixels high?
A2: Picking a color
Questions
1. How can you make pink?
2. How can you make yellow?
3. How can you make purple?
4. How can you make white?
5. How can you make dark gray?
The selection and insertion, are relatively simple, but they are inefficient sequential sorts that use a pair of nested loops and require roughly n^2 comparisons to sort a list of n elements.
More efficient sorts are algorithms that lend themselves to a recursive implementation. In addtion, the Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.
Quick Sort
The quick sort algorithm sorts a list by partitioning the list using an arbitrary chosen partition element and then recursively sorting the sublists on either side of the partition element.
General Strategy:
• First, choose one element of the list to act as a partition element.
• Next, partition the list so that all elements less than the partition element are to the left of that element and all elements greater than the partition element are to the right.
• Finally, apply this quick sort strategy recursively to both partitions.
• The choice of the partition element is arbitrary, we will use the first element in the list.
• For efficiency reasons, it would be nice if the partition element divided the list roughly in half, but the algorithm will work no matter what element is chosen as a partition
Example:
90 65 7 305 120 110 8
we would choose 90 as our partition element.
We would then rearrange the list, swapping the elements that are less than 90 to the left side and those that are greater than 90 to the right side, yielding:
8 65 7 90 120 110 305
We would then apply the quick sort algorithm separately to both partitions. This process continues until a partition contains only one element, which is inherently sorted. Once the initial partition element is determined and placed, it is never considered or moved again.
Here is the book version of the quicksort code:
//-----------------------------------------------------------------
// Sorts the specified array of integers using quick sort.
//-----------------------------------------------------------------
public static void quickSort (int[] numbers)
{
doQuickSort(numbers, 0, numbers.length - 1);
}
//-----------------------------------------------------------------
// Recursively sorts the portion of the given array beginning
// at start and ending at end.
//-----------------------------------------------------------------
private static void doQuickSort (int[] numbers, int start, int end)
{
if (start < end)
{
int middle = partition(numbers, start, end);
doQuickSort(numbers, start, middle);
doQuickSort(numbers, middle + 1, end);
}
}
//-----------------------------------------------------------------
// Partitions the array such that each value in [start, middle]
// is less than or equal to each value in [middle + 1, end].
// The index middle is determined in the procedure and returned.
//-----------------------------------------------------------------
private static int partition (int[] numbers, int start, int end)
{
int pivot = numbers[start];
int i = start - 1;
int j = end + 1;
// As the loop progresses, the indices i and j move towards each other.
// Elements at i and j that are on the wrong side of the partition are
// exchanged. When i and j pass each other, the loop ends and j is
// returned as the index at which the elements are partitioned around.
while (true)
{
i = i + 1;
while (numbers[i] < pivot)
i = i + 1;
j = j - 1;
while (numbers[j] > pivot)
j = j - 1;
if (i < j)
{
int tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
else
{
return j;
}
}
}
Classwork:
1. Trace the quick sort using the data above using the code.
[90, 65, 7, 305, 120, 110, 8]
2. Write the pseudocode looking at the code.
Homework:
4. Under what conditions you have the worse case?
5. What data would yield to a best case and average case?
6. What is the big O notation for this sort for each case?
7. Can you think of a non-recursive QuickSort?
8. Write code for QuickSorting objects. Include compareTo() and toString() methods of the object’s class.
NOTE: WHAT FOLLOWS IS FOR YOUR ENRICHMENT ONLY
It is not part of the AP curriculum.
import java.util.Arrays;
// When we partition data we are dividing it into
// two parts. All items with data above a defined value
// will go in one part and the rest will go in the other
// The value that defines in which group data will go
// is known as the pivot value
public class Partitioning {
private static int[] theArray;
private static int arraySize;
public static void main(String[] args) {
Partitioning partitionArray = new Partitioning(10);
partitionArray.generateRandomArray();
System.out.println(Arrays.toString(Partitioning.theArray));
// Every item smaller than 35 will be on the left and
// everything bigger will be on the right
partitionArray.partitionArray(35);
System.out.println(Arrays.toString(Partitioning.theArray));
}
public void partitionArray(int pivot) {
// If leftPointer finds an item that is greater
// than pivot it stops and waits for the rightPointer
// to find a value less than pivot. Then the items
// are switched
// Starts at the left side of array before index 0
int leftPointer = -1;
// Starts at the right side of the array after the last index
int rightPointer = arraySize;
while (true) {
// Cycle through array until the end is reached
// or an item bigger than pivot is found. Then
// wait for rightPointer to finish cycling
while (leftPointer < (arraySize - 1)
&& theArray[++leftPointer] < pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " in index "
+ leftPointer + " is bigger than the pivot value " + pivot);
// Cycle through array until the beginning is reached
// or an item smaller than pivot is found.
while (rightPointer > 0 && theArray[--rightPointer] > pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[rightPointer] + " in index "
+ rightPointer + " is smaller than the pivot value "
+ pivot);
printHorzArray(leftPointer, rightPointer);
// When the 2 pointers meet at the middle break
// out of the while loop
if (leftPointer >= rightPointer)
break;
else {
// Swap the values in the pointers
swapValues(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " was swapped for "
+ theArray[rightPointer]);
}
}
}
public void swapValues(int indexOne, int indexTwo) {
int temp = theArray[indexOne];
theArray[indexOne] = theArray[indexTwo];
theArray[indexTwo] = temp;
}
Partitioning(int newArraySize) {
arraySize = newArraySize;
theArray = new int[arraySize];
generateRandomArray();
}
public void generateRandomArray() {
for (int i = 0; i < arraySize; i++) {
// Generate a random array with values between
// 10 and 59
theArray[i] = (int) (Math.random() * 50) + 10;
}
}
static void printHorzArray(int i, int j) {
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.format("| %2s " + " ", n);
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.print(String.format("| %2s " + " ", theArray[n]));
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
if (i != -1) {
// Number of spaces to put before the F
int spacesBeforeFront = 5 * i + 1;
for (int k = 0; k < spacesBeforeFront; k++)
System.out.print(" ");
System.out.print("L");
// Number of spaces to put before the R
int spacesBeforeRear = (5 * j + 1 - 1) - spacesBeforeFront;
for (int l = 0; l < spacesBeforeRear; l++)
System.out.print(" ");
System.out.print("H");
System.out.println("\n");
}
}
}
import java.util.Arrays;
// The Quick Sort is normally the fastest sorting algorithm
public class QuickSort {
private static int[] theArray;
private static int arraySize;
public static void main(String[] args) {
QuickSort theSort = new QuickSort(10);
theSort.generateRandomArray();
System.out.println(Arrays.toString(QuickSort.theArray));
theSort.quickSort(0, 9);
System.out.println(Arrays.toString(QuickSort.theArray));
}
QuickSort(int newArraySize) {
arraySize = newArraySize;
theArray = new int[arraySize];
generateRandomArray();
}
public void quickSort(int left, int right) {
if (right - left <= 0)
return; // Everything is sorted
else {
// It doesn't matter what the pivot is, but it must
// be a value in the array
int pivot = theArray[right];
System.out.println("Value in right " + theArray[right]
+ " is made the pivot");
System.out.println("left = " + left + " right= " + right
+ " pivot= " + pivot + " sent to be partitioned");
int pivotLocation = partitionArray(left, right, pivot);
System.out.println("Value in left " + theArray[left]
+ " is made the pivot");
quickSort(left, pivotLocation - 1); // Sorts the left side
quickSort(pivotLocation + 1, right);
}
}
public int partitionArray(int left, int right, int pivot) {
int leftPointer = left - 1;
int rightPointer = right;
while (true) {
while (theArray[++leftPointer] < pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " in index "
+ leftPointer + " is bigger than the pivot value " + pivot);
while (rightPointer > 0 && theArray[--rightPointer] > pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[rightPointer] + " in index "
+ rightPointer + " is smaller than the pivot value "
+ pivot);
printHorzArray(leftPointer, rightPointer);
if (leftPointer >= rightPointer) {
System.out.println("left is >= right so start again");
break;
}
else {
swapValues(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " was swapped for "
+ theArray[rightPointer]);
}
}
swapValues(leftPointer, right);
return leftPointer;
}
public void swapValues(int indexOne, int indexTwo) {
int temp = theArray[indexOne];
theArray[indexOne] = theArray[indexTwo];
theArray[indexTwo] = temp;
}
public void generateRandomArray() {
for (int i = 0; i < arraySize; i++) {
// Generate a random array with values between
// 10 and 59
theArray[i] = (int) (Math.random() * 50) + 10;
}
}
static void printHorzArray(int i, int j) {
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.format("| %2s " + " ", n);
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.print(String.format("| %2s " + " ", theArray[n]));
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
if (i != -1) {
// Number of spaces to put before the F
int spacesBeforeFront = 6 * (i + 1) - 5;
for (int k = 0; k < spacesBeforeFront; k++)
System.out.print(" ");
System.out.print("L" + i);
// Number of spaces to put before the R
int spacesBeforeRear = 5 * (j + 1) - spacesBeforeFront;
for (int l = 0; l < spacesBeforeRear; l++)
System.out.print(" ");
System.out.print("R" + j);
System.out.println("\n");
}
}
}
Turn in the tracing before the end of the period.
Look at the quicksort from the text book and find the difference between the previous one and this one.
Use print statements to trace the swapping of the array elements and compare it to your own tracing.
//********************************************************************
// RecursiveSorts.java Author: Lewis/Loftus/Cocking
//
// Demonstrates the merge sort and quick sort algorithms.
//********************************************************************
public class RecursiveSorts
{
//-----------------------------------------------------------------
// Sorts the specified array of integers using merge sort.
//-----------------------------------------------------------------
public static void mergeSort (int[] numbers)
{
doMergeSort(numbers, 0, numbers.length - 1);
}
//-----------------------------------------------------------------
// Recursively sorts the the portion of the given array beginning
// at start and ending at end.
//-----------------------------------------------------------------
private static void doMergeSort (int[] numbers, int start, int end)
{
if (start < end)
{
int middle = (start + end) / 2;
doMergeSort (numbers, start, middle);
doMergeSort (numbers, middle + 1, end);
merge (numbers, start, middle, end);
}
}
//-----------------------------------------------------------------
// Merges in sorted order the two sorted subarrays
// [start, middle] and [middle + 1, end].
//-----------------------------------------------------------------
private static void merge (int[] numbers, int start, int middle,
int end)
{
// This temporary array will be used to build the merged list.
int[] tmp = new int[end - start + 1];
int index1 = start;
int index2 = middle + 1;
int indexTmp = 0;
// Loop until one of the sublists is exhausted, adding the smaller
// of the first elements of each sublist to the merged list.
while (index1 <= middle && index2 <= end)
{
if (numbers[index1] < numbers[index2])
{
tmp[indexTmp] = numbers[index1];
index1++;
}
else
{
tmp[indexTmp] = numbers[index2];
index2++;
}
indexTmp++;
}
// Add to the merged list the remaining elements of whichever sublist
// is not yet exhausted.
while (index1 <= middle)
{
tmp[indexTmp] = numbers[index1];
index1++;
indexTmp++;
}
while (index2 <= end)
{
tmp[indexTmp] = numbers[index2];
index2++;
indexTmp++;
}
// Copy the merged list from tmp into numbers.
for (indexTmp = 0; indexTmp < tmp.length; indexTmp++)
{
numbers[start + indexTmp] = tmp[indexTmp];
}
}
//-----------------------------------------------------------------
// Sorts the specified array of integers using quick sort.
//-----------------------------------------------------------------
public static void quickSort (int[] numbers)
{
doQuickSort(numbers, 0, numbers.length - 1);
}
//-----------------------------------------------------------------
// Recursively sorts the portion of the given array beginning
// at start and ending at end.
//-----------------------------------------------------------------
private static void doQuickSort (int[] numbers, int start, int end)
{
if (start < end)
{
int middle = partition(numbers, start, end);
doQuickSort(numbers, start, middle);
doQuickSort(numbers, middle + 1, end);
}
}
//-----------------------------------------------------------------
// Partitions the array such that each value in [start, middle]
// is less than or equal to each value in [middle + 1, end].
// The index middle is determined in the procedure and returned.
//-----------------------------------------------------------------
private static int partition (int[] numbers, int start, int end)
{
int pivot = numbers[start];
int i = start - 1;
int j = end + 1;
// As the loop progresses, the indices i and j move towards each other.
// Elements at i and j that are on the wrong side of the partition are
// exchanged. When i and j pass each other, the loop ends and j is
// returned as the index at which the elements are partitioned around.
while (true)
{
i = i + 1;
while (numbers[i] < pivot)
i = i + 1;
j = j - 1;
while (numbers[j] > pivot)
j = j - 1;
if (i < j)
{
int tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
else return j;
}
}
}
//********************************************************************
// Represents a maze of characters. The goal is to get from the
// top left corner to the bottom right, following a path of 1s.
//********************************************************************
public class Maze
{
private final int TRIED = 3;
private final int PATH = 7;
private int stepCount = 0;
private int[][] grid = { {1,1,1},
{1,0,1},
{0,0,1}};
1 1 1
1 0 1
0 0 1
//-----------------------------------------------------------------
// Tries to recursively follow the maze.
//-----------------------------------------------------------------
public boolean traverse (int row, int column)
{
boolean done = false;
if (valid (row, column))
{
grid[row][column] = TRIED; // this cell has been tried
if (row == grid.length-1 && column == grid[0].length-1)
done = true; // the maze is solved
else
{
done = traverse (row+1, column); // down
if (!done)
done = traverse (row, column+1); // right
if (!done)
done = traverse (row-1, column); // up
if (!done)
done = traverse (row, column-1); // left
}
if (done) // this location is part of the final path
{
grid[row][column] = PATH;
stepCount--;
}
}
return done;
}
//-----------------------------------------------------------------
// Determines if a specific location is valid.
//-----------------------------------------------------------------
private boolean valid (int row, int column)
{
boolean result = false;
stepCount++;
// check if cell is in the bounds of the matrix
if (row >= 0 && row < grid.length &&
column >= 0 && column < grid[row].length)
// check if cell is not blocked and not previously tried
if (grid[row][column] == 1)
result = true;
return result;
}
//-----------------------------------------------------------------
// Returns the maze as a string.
//-----------------------------------------------------------------
public String toString ()
{
String result = "\n";
for (int row=0; row < grid.length; row++)
{
for (int column=0; column < grid[row].length; column++)
result += grid[row][column] + "";
result += "\n";
}
return result;
}
}
//********************************************************************
// MazeSearch.java Author: Lewis/Loftus/Cocking
// Demonstrates recursion.
//********************************************************************
public class MazeSearch
{
//-----------------------------------------------------------------
// Creates a new maze, prints its original form, tries to
// solve it, and prints out its final form.
//-----------------------------------------------------------------
public static void main (String[] args)
{
Maze labyrinth = new Maze();
System.out.println (labyrinth);
if (labyrinth.traverse (0, 0))
System.out.println ("The maze was successfully solved!");
else
System.out.println ("There is no possible path.");
System.out.println (labyrinth);
}
}
Assignment:
1. Maze 3 by 3 solver trace
Show the rows and columns visited by the program for this maze:
1 0 1
1 1 1
0 1 1
2. Maze 3 by 3 solver trace using stacks
Show the changes in the stacks as the visit to a path pushes the location information and then the values are pop when they are not part of the solution.
NOTE: If you want to use small pieces of paper to push information into the top of the stack, I have a good number of them for you to use.
Here is the trace for the 3 by 3 above:
(row,column)
( 0 , 0)
( 1 , 0)
( 2 , 0)
( 1 , 1)
( 0 , 0)
( 1 , -1)
( 0 , 1)
( 1 , 1)
( 0 , 2)
( 1 , 2)
( 2 , 2)
