Polygon Perimeter

Description:

You have a rectangular white board with some black cells. The black cells create a connected black figure, i.e. it is possible to get from any black cell to any other one through connected adjacent (sharing a common side) black cells.

Find the perimeter of the black figure assuming that a single cell has unit length.

It’s guaranteed that there is at least one black cell on the table.

Example

  • For
    matrix = [[false, true,  true ],
              [true,  true,  false],
              [true,  false, false]]
    

    the output should be
    polygonPerimeter(matrix) = 12.

  • For
    matrix = [[true, true,  true],
              [true, false, true],
              [true, true,  true]]
    

    the output should be
    polygonPerimeter(matrix) = 16.

Input/Output

  • [time limit] 3000ms (java)
  • [input] array.array.boolean matrix

    A matrix of booleans representing the rectangular board where true means a blackcell and false means a white one.

    Constraints:
    2 ≤ matrix.length ≤ 5,
    2 ≤ matrix[0].length ≤ 5.

  • [output] integer

Tests:
Solution(Java):

int polygonPerimeter(boolean[][] matrix) {
    int perimeter = 0;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (i - 1 < 0 && matrix[i][j]) {
                perimeter++;
            }
            if (i + 1 == matrix.length && matrix[i][j]) {
                perimeter++;
            }
            if (j - 1 < 0 && matrix[i][j]) {
                perimeter++;
            }
            if (j + 1 == matrix[0].length && matrix[i][j]) {
                perimeter++;
            }
            if (matrix[i][j] && 0 <= i - 1) {
                if (!matrix[i - 1][j]) {
                    perimeter++;
                }
            }
            if (matrix[i][j] && i + 1 < matrix.length) {
                if (!matrix[i + 1][j]) {
                    perimeter++;
                }
            }
            if (matrix[i][j] && 0 <= j - 1) {
                if (!matrix[i][j - 1]) {
                    perimeter++;
                }
            }
            if (matrix[i][j] && j + 1 < matrix[0].length) {
                if (!matrix[i][j + 1]) {
                    perimeter++;
                }
            }
        }
    }
    return perimeter;
}

 

Advertisements

One thought on “Polygon Perimeter

  1. Spencer says:

    Heres a JS version, I think my algorithm is essentially the same, just looks better

    function polygonPerimeter(matrix) {
    //Tally of perimeter
    var perimeter = 0

    //Function to count perimeter of given square
    var count = (x, y) => {

    //Whats the count
    var cnt = 0

    //We need to check NSEW squares
    var arr = [[0, -1], [0, 1], [-1, 0], [1, 0]]

    //Foreach direction
    arr.forEach((e, i, a) => {
    //Coordinates of neighbor square
    var X = x+e[0], Y = y+e[1]

    //If we are outside the matrix increase cnt and do nothing else
    if(X = matrix.length || Y = matrix[X].length) {
    cnt++
    return
    }

    //If the neighbor is black, do nothing
    if(matrix[X][Y])
    return

    //Neighbor is white, increase cnt
    cnt++
    })
    return cnt
    }

    //For every square
    for(var i=0; i<matrix.length; i++)
    for(var j=0; j<matrix[0].length; j++)
    if(matrix[i][j]) //If square is black
    perimeter += count(i, j) //Get perimeter of this square
    //Return the perimeter
    return perimeter
    }

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s