Skip to content

B. Lawnmower

The Lawnmower is the problem B of the Google Code Jam 2013 Qualification round.

The suggested solution in the Contest analysis is to try to cut grace on every row and column to the maximum height found on this row or column then compare the pattern got with the pattern given.

My approach is different. For any given cell on the lawn we can detect is there a cell with bigger height on a way to the border (we check for all four directions), if so we can't not cut on this direction to achieve desired pattern. The advantage of this solution is that we can detect negative answer much quicker.

Here is my solution for this problem in C language:


#include <stdio.h>

main() {
  int i, T, M, N, n, m, x;
  int res;

  scanf("%d\n", &T);
  for (i = 0; i < T; i++) {
    printf("Case #%d: ", i + 1);
    scanf("%d %d\n", &N, &M);
    {
      int L[N][M];
      res = 1;
      for (n = 0; n < N; n++) {
	for (m = 0; m < M; m++) {
	  scanf("%d", &L[n][m]);
	}
      }
      for (n = 0; n < N && res; n++) {
	for (m = 0; m < M && res; m++) {
	  int res1 = 1, res2 = 1, res3 = 1, res4 = 1;
	  for (x = m - 1; x >= 0 && res1; x--) if (L[n][m] < L[n][x]) res1 = 0;
	  for (x = m + 1; x < M && res2; x++) if (L[n][m] < L[n][x]) res2 = 0;
	  if ((res1 + res2) != 2) {
	    for (x = n - 1; x >= 0 && res3; x--) if (L[n][m] < L[x][m]) res3 = 0;
	    for (x = n + 1; x < N && res4; x++) if (L[n][m] < L[x][m]) res4 = 0;
	  }
	  if ((res1 == 1 && res2 == 1) || (res3 == 1 && res4 == 1)) {
	    res = 1;
	  } else res = 0;
	}
      }
      if (res) printf("YES\n");
      else printf("NO\n");
    }
  }
}

Leave a Reply

Your email address will not be published.