Analysis: Perimeter by Fatih Gelgi and Brian Dean


This problem can be solved by simulating the tour around the bales. Consider the example given in the problem (including the borders of the cells):

.-.-.
|X|X| 
.-.-.-.-.
|X| |X|X|
.- - -.-. 
|X|X|X|
.-.-.-.

We just need to walk on the outer border of the cells of the hay bales. Walking outside the border can be accomplished by right hand rule: keep your right hand on the wall when walking. Try to turn right first. If not available use the current direction. If current direction is also not available then turn left.

    S
    |X X 
v-<-<
|X X

In the figure above, S is the starting location and the direction is south. Move one step to south then we can turn to right. But in the next step, we cannot turn right hence continue walking one more step. Now we cannot turn right or continue walking in the same direction. So we have to run left this time and so on. At the end of the walk, we come back to the starting location. First we should determine a starting location and the direction. Top leftmost corner is a reasonable place to start (shown with 'S' in the following figure) and the direction can be either south or east -- suppose we choose south.

S-<-<
|X X| 
v   ^-<-<
|X   X X|
v     >-^ 
|X X X|
>->->-^

To implement the idea we can use a matrix say mat. In the problem (1,1) is the lower-left cell. Actually, it doesn't matter; we can use matrix (row,column) as the cell locations. In this case, the shape will be flipped but the perimeter will be same. In this setting, notice that our walking coordinates are different than matrix cell locations. We consider (1,1) is the top-left corner of the cell (1,1) and its bottom-right corner is (2,2).

(1,1).-.(1,2)
     |X|
     .-.
(2,1)   (2,2)

Hence, to check if south direction of (y,x) is available when walking, mat[y][x] must contain a bale. Similarly, mat[y-1][x-1] has to be occupied for north, mat[y-1][x] for east and mat[y][x-1] for west.

Here's a sample solution:

#include <fstream>

using namespace std;

// directions: down,right,up,left
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int mat[102][102],perimeter,sy=100,sx=100,d;

int main()
{
	ifstream fin("perimeter.in");
	int n,x,y;
	fin >> n;
	for (int i=0; i<n; i++)
	{
		fin >> x >> y;
		mat[y][x]=1;
		// update starting postion
		//   the upper-leftmost corner of the shape
		if (y<sy || (y==sy && x<sx)) sy=y,sx=x;
	}
	fin.close();

	// walk around the bales using right hand rule
	y=sy,x=sx;
	do
	{
		// update coordinates with respect to the direction
		y+=dir[d][0],x+=dir[d][1],perimeter++;
		// determine new direction
		// 		start from previous direction to search
		for (d=(d+3)%4; ; d=(d+1)%4)
			// check neighbor bale locations based on direction
			if ((d==0 && mat[y][x]) || (d==1 && mat[y-1][x]) ||
			(d==2 && mat[y-1][x-1]) || (d==3 && mat[y][x-1])) 
				break;
	}
	// continue until coming back to the starting location
	while (y!=sy || x!=sx);

	ofstream fout("perimeter.out");
	fout << perimeter << endl;
	fout.close();
}

An alternative approach is to do a recursive "flood fill" of the grid containing our object, starting from a cell that is definitely outside the object such as (0,0). That is, whenever we visit a cell, we mark it as having been visited (to avoid cycling) and then recursively visit its 4 neighbors, as long as these neighbors are empty cells. If we check a neighboring cell that is occupied with part of the object, we increment our perimeter count instead of visiting that cell recursively.

Brian Dean's recursive solution in C looks like this:

#include <stdio.h>
#define MAX_N 100

int already_visited[MAX_N+2][MAX_N+2];
int occupied[MAX_N+2][MAX_N+2];
int perimeter;

int valid(int x, int y)
{
  return x>=0 && x<=MAX_N+1 && y>=0 && y<=MAX_N+1;
}

void visit(int x, int y)
{
  if (occupied[x][y]) { perimeter++; return; }
  if (already_visited[x][y]) return;
  already_visited[x][y] = 1;
  if (valid(x-1,y)) visit(x-1,y);
  if (valid(x+1,y)) visit(x+1,y);
  if (valid(x,y-1)) visit(x,y-1);
  if (valid(x,y+1)) visit(x,y+1);
}

int main(void)
{
  int N, i, x, y;
  
  freopen ("perimeter.in", "r", stdin);
  freopen ("perimeter.out", "w", stdout);

  scanf ("%d", &N);
  for (i=0; i<N; i++) {
    scanf ("%d %d", &x, &y);
    occupied[x][y] = 1;
  }

  visit(0,0);

  printf ("%d\n", perimeter);
  return 0;
}