TopCoder Problem Statement - Orchard |

Single Round Match 167 Round 1 - Division II, Level Three |

Determine the position in an NxN array that is furthest from the edges, and from any tree.

1 public class Orchard { 2 3 int size; 4 int[][] distances; 5 6 public int[] nextTree(String[] orchard) { 7 8 size = orchard.length; 9 10 distances = new int[size][size]; 11 12 /* 13 * Mark distances from the edges. 14 * This create concentric squares with the distance 15 * at the edges = 1, and the value increasing by 16 * 1 as the squares move inward. 17 */ 18 for (int i = 0; i < (size + 1) / 2; i++) { 19 for (int j = i; j < (size - i); j++) { 20 distances[i][j] = i + 1; // Top Row 21 distances[size - 1 - i][j] = i + 1; // Bottom Row 22 distances[j][i] = i + 1; // Left Column 23 distances[j][size - 1 - i] = i + 1; // Right Column 24 } 25 } 26 27 /* 28 * Add trees into the mix 29 * Updates the values in the distance matrix. 30 */ 31 for (int row = 0; row < size; row++) { 32 for (int col = 0; col < size; col++) { 33 if ('T' == orchard[row].charAt(col)) { 34 placeTree(row,col); 35 } 36 } 37 } 38 39 /* 40 * Find and return the greatest distance 41 */ 42 int maxDistance = 0; 43 int[] retValues = new int[] {1, 1}; 44 45 for (int y = 0; y < size; y++) { 46 for (int x = 0; x < size; x++) { 47 if (distances[y][x] > maxDistance) { 48 maxDistance = distances[y][x]; 49 retValues[0] = y + 1; 50 retValues[1] = x + 1; 51 } 52 } 53 } 54 55 return retValues; 56 } 57 58 59 /* 60 * Places a tree at the given coordinate. Then works outward from the 61 * tree's location reducing the distances of it's neighboring squares. 62 * Here's where all the work of updating the distances matrix is done. 63 */ 64 private void placeTree(int row, int col) { 65 66 // Work the area above the tree. 67 for (int dy = 0; row - dy >= 0; dy++) { 68 69 // Reduce neighbors above and to the left. 70 for (int dx = 0; col - dx >= 0; dx++) { 71 distances[row - dy][col - dx] = 72 Math.min(distances[row - dy][col - dx], dx + dy); 73 } 74 75 // Reduce neighbors above and to the right. 76 for (int dx = 0; col + dx < size; dx++) { 77 distances[row - dy][col + dx] = 78 Math.min(distances[row - dy][col +dx], dx + dy); 79 } 80 } 81 82 // Works the area below the tree 83 for (int dy = 0; row + dy < size; dy++) { 84 85 // Reduce neighbors below and to the left. 86 for (int dx = 0; col - dx >= 0; dx++) { 87 distances[row + dy][col - dx] = 88 Math.min(distances[row + dy][col - dx], dx + dy); 89 } 90 91 // Reduce neighbors below and to the right. 92 for (int dx = 0; col + dx < size; dx++) { 93 distances[row + dy][col + dx] = 94 Math.min(distances[row + dy][col +dx], dx + dy); 95 } 96 } 97 } 98 99 }

There are several way to go about solving this problem. I've seen it solved using breadth-first search from every point in the grid. But, I believe this solution takes a far easier approach.

The idea is to create an NxN array that holds the distances from each point to and edge or a tree, then we can just scan through the distances array looking for the largest value. The loops on lines 18 - 25 initialize the array so that all elements on the outer edge have a value of 1. Then each concentric square moving inward gets increasing values. A 5x5 square, would look like this:

1 | 1 | 1 | 1 | 1 |

1 | 2 | 2 | 2 | 1 |

1 | 2 | 3 | 2 | 1 |

1 | 2 | 2 | 2 | 1 |

1 | 1 | 1 | 1 | 1 |

Next, each tree is dropped into the matrix. The placeTree() method handles reducing the distance values in the matrix based on their proximity to the new tree. The method begins at the tree's location and then works by going upward one row at a time, first working to the left and then right. At each new location it determines if that distance should be reduced to the distance back to the tree, or left alone because its value was already smaller. After reaching the top of the matrix, the method starts over from the tree's location and works down to the bottom. Using the above example, a tree placed at location 2,1 would update the matrix to be:

1 | 1 | 1 | 1 | 1 |

1 | 1 | 2 | 2 | 1 |

1 | 0 | 1 | 2 | 1 |

1 | 1 | 2 | 2 | 1 |

1 | 1 | 1 | 1 | 1 |

After all the trees have been placed, then it's a simple matter of looping through the distances array, and finding the largest value.

## No comments:

## Post a Comment