Second example problem:
Given an m * n field of trees and open spaces, find out the biggest square house that can be built with no intersection with trees.
For a suboptimal solution, simple solution starts with scanning every space to see if it is open or not (starting in the upper-left). Find the largest possible square starting at the given space, then find the maximum size square possible in the entire area.
Note that each loop has two conditions, the total width/height of the area AND the max value. This max-value check keeps the loops from searching for open squares that could not possibly be larger than the current largest square (e.g. too close to one edge of the area).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Loop through every possible square in the forest. // Note: Stop if our current x or y could not possibly // lead to a larger square (i.e. the spaces in the remaining // area are less than the largest square currently found. for (y = 0; y < height && (height - y > max); y++) { for (x=0; x < width && (width -x > max); x++) { tot++; // If we find an empty spot, use it as the top-left // corner, and attempt to find the largest square // that can be made from said location without // containing any trees. if (forest[y*width+x] == 0) { max = std::max(max,Find2(forest,max, x,y,tot,false)); } } } |
Now, the function itself, starting at the specified location, searches diagonally for trees, stopping at the first and/or nearest tree it encounters. It does this by first checking the current square for a tree. If there is no tree it scans downward until it a) finds a tree or b) reaches the edge of the map. It repeats the process to the right. It then increments the “top-left” square inward and repeats the process.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
// This is a working solution. See comments inline. int Find2(const char * forest, int curmax, int x, int y, int &tot, bool usefound) { // Note, in the code below, max can only shrink, // it can never grow. Therefore, set max to the // maximum possible size based on available space // in the forest. int max = std::min(width-x,height-y); // Starting at X,Y, going until we've reached the edge // of the field or we've stopped at a smaller square // than our previous maximum... for (int lcv = 0; lcv < max && max > curmax; lcv++) { tot++; int pos = (y+lcv)*width + x + lcv; // If we have already computed a "rough max" // (looking only down and right), use that value // without checking it again. if (usefound && FoundMax.find(pos) != FoundMax.end()) { max = FoundMax[pos]; } // Otherwise, search for the new max. else { // If the current spot is a tree, this is our max. if (forest[pos] == 1) { max = lcv; } // Otherwise, try right and down to see where the // next tree is. else { // Go down, find the first tree or the end of // the field/current max. By definition of the // loop bounds, any tree we find is a new, smaller max. for (int y3 = lcv+1; y3 < max; y3++) { tot++; if (forest[(y+y3)*width + x+lcv] == 1) { max = y3; } } // Now, search right, finding the first tree. // Note that we will exit the loop once we have // hit the current max, either the edge of the // forest, of the x or y value of the nearest tree. for (int x3 = lcv+1; x3 < max; x3++) { tot++; if (forest[(y+lcv)*width + x+x3] == 1) { max = x3; } } } // end if not currently on a tree. // set the found value here for future calls to this function. FoundMax[pos] = max; } // end else no FoundMax } // end of for each x,y pair. return max; } |
The code above has one special optimization. We first declare a global variable std::unordered_map<int,int> FoundMax; This unordered (hash) map is keyed on the x,y coordinates of a square, and stores the maximum size of a square found starting at those coordinates. This way, it we happen to be searching a diagonal sub-set of a previously searched larger square, we will not have to loop further to find the area of that square. Note that because this searching works diagonally, we could actually use membership in the FoundMax map as an exit condition (or perhaps, in the outer main loop to prevent calling Find2 in the first place).
The complexity of this algorithm is N for the outer-most loop (once for each square). From each square, we search a maximum of M additional squares (where M < N), making for a worst-case complexity of O(n*m). This isn’t a valid expression, true, and by investigation we can see that m decreases logarithmically with respect to n, making a true complexity of O(n log(n)).
Ideas for further optimization: For all upper-left squares with the same X value, the maximum distance down is less than the maximum distance of the previous Y value down. We could therefore skip searching for the next downward tree with a lookup of the nearest downward tree from Y-1 (if we were storing that value). The same goes for the nearest tree to the right from the current X for squares starting on the same Y.