Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Help with an assignment ...

AKI_SERAKI_SER Member Posts: 1
[code]Shumadija (a Serbian province) was once full of forests, but it can't be proud of them anymore. A huge effort is being made to prevent trees from being unnecessarily cut down. A local newcomer, who is also a very rich man, bought a relatively large piece of land (square-shaped), and he wants to build a house on it. He also wants to make the house as large as possible and and square-shaped with its sides parallel to the sides of the land that the house will be built on.

The land is divided into little 1x1 squares. One tree occupies exactly one square. Since the land is big, it's very hard to find the largest square with its sides parallel to the sides of the land and with no trees on it. For a given map of the land that describes the position of all the trees, you must find the square with the largest sides and with no trees on it. The length of the square's side is the number of 1x1 squares along its side.

INPUT:
The input is read from the standard input. The first line of input contains a number N ( N <= 200) that tells the length of the land's sides. In the next line there will be a number P , which is the number of trees positioned on this land. The next P lines contain two numbers that represent the coordinates of a tree.

OUTPUT:
One and only line of the standard output should have only one number, which tells the length of the side of the largest square with no trees in it.

Input:
5
3
2 2
4 2
4 4

Output:
3

Explanation:
Coordinates of upper-left point of square are (1,3) and lower-right (3,5).[/code]
That's my assignment,I'm still a beginner in coding with Pascal,so I would appreciate some help...

Comments

  • AtexAtex Member Posts: 268
    [code][color=Blue]
    program trees_and_clearing;

    const _n_max_=200; {Maximum square side}
    {Global variables}
    var f{orest}:array[1.._n_max_,1.._n_max_] of boolean;
    { 2 dimensional array; 0 - empty , 1 - tree }
    n:byte;

    { This routine checks for the biggest clearing in the forest,
    returns the first occurrence starting from 1,1
    E.g. If n=7 tree1=(6,2) tree2=(2,6) Then would return 5x5 @ (1,1),
    But there is also another 5x5 clearing @ (3,3)
    To check for multiple solutions this code has to be modified.
    This probably not the best approach, but was quite simple to implement.
    The idea is to start with the biggest possible square: (n-1), because
    is at least one tree there (with 0 trees, is no point calling this routine),
    if this located on the perimeters than it would allow for n-1 size for
    clearing. Now position this imaginary clearing onto the grid ( forest ),
    from (1,1) to any possible location given that the clearing is inside
    the grid. Check if there are any trees in the way at each position, if
    none than return current size and coordinate. If are trees in the way
    than update position to a new one, when ran out of possibilities decrease
    clearing size and start over from (1,1). The whole thing could be optimized
    to skip some loops ( E.g. If a 5x5 clearing @ (1,1) meets a tree let say
    @ (3,3), to skip steps 2..3,2..3, thus saving some time ), but I don't
    think the speed is an issue here, especially with small arrays }

    procedure get_biggest_house(var size,xpos,ypos:byte);
    var tree{ in the way}:boolean;
    y,x:byte;
    size_,xpos_,ypos_:byte; {TP doesn't let return values to control for's}
    begin
    for size_:=pred(n) downto 1 do begin {pred(n) because there is at least one tree}
    size:=size_; {Set return value}
    for ypos_:=1 to succ(n-size) do begin
    ypos:=ypos_; {Set return value}
    for xpos_:=1 to succ(n-size) do begin
    xpos:=xpos_; {Set return value}
    tree:=false; {init trigger with 0}
    for y:=ypos to pred(ypos+size) do
    for x:=xpos to pred(xpos+size) do
    if f[x,y] then tree:=true; {If at least one tree in the way set trigger}
    if not(tree) then exit; {Trigger wasn't set, exit procedure}
    end;end;end;end;


    {Local variables}
    var i,x,y:byte;
    tree_max,no_of_sq{uares}:word;

    {Main, probably an overkill, but forces user to enter the right data}
    begin
    writeln;
    fillchar(f,sizeof(f),false); {Initiate f with 0's}
    repeat { This forces the user to enter a correct value 1.._n_max_ }
    write('Enter square side [3..',_n_max_,'] : ');readln(n);
    until n in [3.._n_max_];
    no_of_sq:=sqr(n); { Calculate no of squares }
    writeln;
    {My preference was to use repeat..until vs. while..end loops,
    because there's no need to initiate control variable(s),
    BTW none of the loop types are inferior to each other}
    repeat
    write('Enter the number of trees [0..',no_of_sq,'] : ');readln(tree_max);
    until tree_max in [0..no_of_sq];
    if tree_max=0 then writeln('No trees, biggest house = ',n,'x',n) else
    if tree_max=no_of_sq then writeln('No room to build') else begin
    {The FOR loops are basically WHILE..END loops with automatic
    control boundary check and incrementation}
    for i:=1 to tree_max do begin
    repeat {#13#10 acts as a "writeln"}
    write(#13#10,'Enter X coord. for tree no. ',i,' [1..',n,'] : ');readln(x);
    write('Enter Y coord. for tree no. ',i,' [1..',n,'] : ');readln(y);
    until (x in [1..n]) and (y in [1..n]);
    if f[x,y] then begin
    writeln('Duplicate coordinate, try again');
    dec(i); {is possible to alter the FOR loop control}
    end else f[x,y]:=true;
    end;
    writeln;
    get_biggest_house(i,x,y);
    writeln('The biggest house is: ',i,'x',i,'. Upper left corner is at: ',x,',',y);
    end;
    end.
    [/color][/code]
Sign In or Register to comment.