Computer Science Canada

Answer to J5/S3 Floor Plan (2003) CCC??????

Author:  nate [ Fri Feb 20, 2004 7:19 pm ]
Post subject:  Answer to J5/S3 Floor Plan (2003) CCC??????

I was wondering, being so close to writting the CCC does anyone have a working answer to J5/S3 Floor Plan (2003) CCC, in java or turing. It would be really helpful if i could understand. Tony tried to help me but if you had code that would be much easy.

Thanks

Author:  Andy [ Sat Feb 21, 2004 11:57 am ]
Post subject: 

i did it using whatdotcolor.... check it out here

http://www.compsci.ca/v2/viewtopic.php?t=2381

Author:  nate [ Sat Feb 21, 2004 3:26 pm ]
Post subject: 

i read your comments but could u really explain how you are figuing out how many rooms there are?

thanks

Author:  zylum [ Sat Feb 21, 2004 7:40 pm ]
Post subject: 

here's my way sorry i dont have time to comment it, i'll put a commented version up tomorrow.. and it's a bit messy, sorry for that too...

code:

%website:  http://contest-cemc.uwaterloo.ca/ccc/sitemap.shtml
var inFile : int
var fileName : string := "FLOOR5.IN.txt"
open : inFile, fileName, get

var rows, cols, totalTiles : int

get : inFile, totalTiles
get : inFile, rows
get : inFile, cols

var tiles : array 1 .. cols, 1 .. rows of int
var tempRows : array 1 .. rows of string
var letter : string

for row : 1 .. rows
    get : inFile, tempRows (row)
end for

for col : 1 .. cols
    for row : 1 .. rows
        letter := tempRows (row) (col)
        if letter = "I" then
            tiles (col, row) := 0
        else
            tiles (col, row) := 1
        end if
    end for
end for

/*****************************************************************************
 ******************************************************************************
 *****************************************************************************/

var usedTiles : int := 0
var roomSize : array 1 .. 1000 of int
var OPEN, CLOSED : array 1 .. cols, 1 .. rows of int

for i : 1 .. 1000
    roomSize (i) := 0
end for

for i : 1 .. cols
    for j : 1 .. rows
        OPEN (i, j) := 0
        CLOSED (i, j) := 0
    end for
end for

var found : int
procedure findRoom
    found := 0
    for tx : 1 .. cols
        for ty : 1 .. rows
            if tiles (tx, ty) = 1 and CLOSED (tx, ty) = 0 then
                OPEN (tx, ty) := 1
                found := 1
                exit when found = 1
            end if
        end for
        exit when found = 1
    end for
end findRoom

procedure checkTiles (strtX, strtY : int)
    if CLOSED (strtX, strtY) = 0 then
        usedTiles += 1
        CLOSED (strtX, strtY) := 1
        OPEN (strtX, strtY) := 0
        if strtX > 1 then
            if CLOSED (strtX - 1, strtY) = 0 and OPEN (strtX - 1, strtY) = 0 and tiles (strtX - 1, strtY) = 1 then
                OPEN (strtX - 1, strtY) := 1
            end if
        end if
        if strtX < cols then
            if CLOSED (strtX + 1, strtY) = 0 and OPEN (strtX + 1, strtY) = 0 and tiles (strtX + 1, strtY) = 1 then
                OPEN (strtX + 1, strtY) := 1
            end if
        end if

        if strtY > 1 then
            if CLOSED (strtX, strtY - 1) = 0 and OPEN (strtX, strtY - 1) = 0 and tiles (strtX, strtY - 1) = 1 then
                OPEN (strtX, strtY - 1) := 1
            end if
        end if
        if strtY < rows then
            if CLOSED (strtX, strtY + 1) = 0 and OPEN (strtX, strtY + 1) = 0 and tiles (strtX, strtY + 1) = 1 then
                OPEN (strtX, strtY + 1) := 1
            end if
        end if
    end if
end checkTiles

var sx, sy : int := 1
var check : int := 0
procedure explore
    check := 0
    for tx : 1 .. cols
        for ty : 1 .. rows
            if OPEN (tx, ty) = 1 then %and CLOSED (tx, ty) = 0 and tiles (tx, ty) = 1 then
                check := 1
                sx := tx
                sy := ty
                exit when check = 1
            end if
        end for
        exit when check = 1
    end for
end explore

var room : int := 1
findRoom
loop
    explore
    checkTiles (sx, sy)
    if check = 0 then
        roomSize (room) := usedTiles
        usedTiles := 0
        room += 1
        findRoom
    end if
    exit when found = 0
end loop

room := 0
for i : 1 .. 1000
    if roomSize (i) > 0 then
        room += 1
    end if
    exit when roomSize (i) = 0
end for

%sort rooms
var temp : int
for i : 1 .. room
    for j : 1 .. room - 1
        if roomSize (j) < roomSize (j + 1) then
            temp := roomSize (j)
            roomSize (j) := roomSize (j + 1)
            roomSize (j + 1) := temp
        end if
    end for
end for

var rooms : int := 0
for i : 1 .. room
    exit when totalTiles - roomSize (i) < 0
    if totalTiles - roomSize (i) >= 0 then
        totalTiles -= roomSize (i)
        rooms += 1
    end if
end for


put rooms, " rooms, ", totalTiles, " square meters left over"


close : inFile

Author:  Andy [ Sun Feb 22, 2004 1:53 pm ]
Post subject: 

wow that is so much longer... for my way, i just draw fill then count how many different color there are

Author:  zylum [ Sun Feb 22, 2004 8:23 pm ]
Post subject: 

i MUST admit, good effort on your part but you'd only get 12/15 where as i'd get full marks... what i mean is that your output for test 3 is 8 rooms 2 square meters left over while the answer is 5 rooms 2 square meters left over...

-zylum

Author:  AsianSensation [ Tue Feb 24, 2004 7:52 am ]
Post subject: 

or since this is almost a standard maze question, we could all just use recursion and forget about whatdotcolor?

Author:  zylum [ Tue Feb 24, 2004 3:57 pm ]
Post subject: 

good idea Very Happy


: