LargestCircle – TopCoder

LargestCircle – TopCoder SRM 212 Div 2 (3rd problem):

This problem does not require any algorithm to solve, rather it was hard to figure out how to find cells that constitute the circle.
We need to consider all four vertexes in the cell.
Let's look at 4*4 grid for simplicity.

When we defining our cell structure, we have four vertexes in each cell.
Considering (2,2) as the center, look at the cell (0,0). There are four vertexes (0,0),(0,1),(1,0),(1,1).
Let's look at the distance from (2,2) to these four points.
(0,0) ~ 2.8 ( because it is 2 x sqrt(2))
(0,1) ~ 2.2 ( sqrt(5))
(1,0) ~ 2.2 ( sqrt(5))
(1,1) ~ 1.4 ( sqrt(4))
If we want to draw a circle with radius 2, and we observe that the cells were passed onto the circle.
The four points in each cell bounded by between 1 to 3.
More precisely, the distance from center to any points in the cell falls between r - 1 and r + 1, inclusively.
So, we are able to solve this problem with brute-force, from the beginning to the end of the cells.
At each cell, we try all circles we can make, and choose the maximum.

Here is my complete code.


public class LargestCircle {
      public int radius(String[] grid) {
           boolean[][] cells = new boolean[50][50];
           int row = grid.length;
           int col = grid[0].length();
           if (row == 1 || col == 1)
                return 0;
           for (int i=0;i<row;i++) {
                for (int j=0;j<col;j++) {
                     if (grid[i].charAt(j) == '.')
                          cells[i][j] = true;
                }
           }
           int radius = 0;
           for (int i=0;i<row;i++) {
                for (int j=0;j<col;j++) {
                     int temp = getCircle(cells,i,j);
                     if (temp > radius)
                          radius = temp;
                }
           }
           //TODO
           return radius;
      }
      public int getCircle(boolean[][] cells, int x, int y) {
           for (int i=25;i>0;i--) {
                boolean success = true;
                for (int j=x-i;j<x+i;j++) {
                     for (int k=y-i;k<y+i;k++) {
                          // check the boundary
                          if (!checkBoundary(cells,x,y,j,k,i)){
                               success = false;
                               break;
                          }
                     }
                }
                if (success)
                     return i;
           }
           return 0;
      }
      public boolean checkBoundary(boolean[][] cells, int x, int y, int i, int j, int radius) {
     int[] dx = {0,1,1,0};
     int[] dy = {0,0,1,1};
     double[] r_array = new double[4];
     boolean result = true;
     if (i < 0 || j < 0 || i > 49 || j > 49)
       return false;
     for (int m=0;m<4;m++) {
       int xDif = x-(i+dx[m]);
       int yDif = y-(j+dy[m]);
       double r = Math.sqrt(xDif*xDif + yDif*yDif);
       r_array[m] = r;
     }
     boolean allSatisfy = true;
     for (int m=0;m<4;m++) {
       if (r_array[m] < (radius - 1) || r_array[m] > (radius + 1))
         allSatisfy = false;
     }
     if (allSatisfy && !cells[i][j])
       result = false;
     return result;
   }
 }