Split your land and get smaller lands !

First, you have a land (1,1)(n,n)

For example:

Your land:

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

after adding the land with maximal importance:

1 1 1 1 1 1
1 1 1 1 1 1
1 1 9 9 1 1
1 1 9 9 1 1
1 1 1 1 1 1
1 1 1 1 1 1

You have 4 new lands:

2 lands:

a a a a a a
a a a a a a
1 1 9 9 1 1
1 1 9 9 1 1
a a a a a a
a a a a a a

and 2 lands:

a a 1 1 a a
a a 1 1 a a
a a 9 9 a a
a a 9 9 a a
a a 1 1 a a
a a 1 1 a a

For each of your new lands, you continue add other lands with decreasing importance.

Finally, you will find out that after adding a land with a certain importance t, you can't create a land with desired park size. Now, you end your program and output t.

THE END ^^!







Edited by author 08.10.2010 14:39

Edited by author 12.10.2010 10:14

Hmmm....
I've tried this strategy using BFS and got ML3. Using recursion TL3.
So probably i'm missing something.
here is pseudo code for my recursive solution


int findMin(List<Rectangle> lands, Rectangle area, int startFrom) {
 if (minSide(area) < regionSize) return startFrom - 1;
 Rectangle land = firstLandThatIntersectsArea(lands, area, startFrom);
 if (land == null) return 1;
 findMin(lands, top(area, land), indexOf(land) + 1);
 findMin(lands, right(area, land), indexOf(land) + 1);
 findMin(lands, bottom(area, land), indexOf(land) + 1);
 findMin(lands, left(area, land), indexOf(land) + 1);
}

call findMin(sortedDescByPriority(lands), new Rectangle(1, 1, n, n), 0);

Send me the code, please!

goldenxbullet@gmail.com

Thanks!

Algorithm! AC 0.001
1. use buffered i/o.

2. check only on row = build_row + build_side, and col = build_col + build_side  coordinates. its very simple.
More formal:
let build structure:  struct build{  int priority; int len; int row; int col; }
build d[M];
int L, A;  // L - length of square city, A - length of building Park .
so need to check only (think about it!!!)
  row = d[i].row + d[i].len ;
  col = d[j].col + d[j].len ;  i=0..M-1,j=0..M-1 coordinates. Good Luck!!!

Don't forget also, for row + A-1 <= L  and col + A - 1 <= L