----------------------------------- nate Fri Feb 20, 2004 7:19 pm 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 ----------------------------------- Andy Sat Feb 21, 2004 11:57 am ----------------------------------- i did it using whatdotcolor.... check it out here http://www.compsci.ca/v2/viewtopic.php?t=2381 ----------------------------------- nate Sat Feb 21, 2004 3:26 pm ----------------------------------- i read your comments but could u really explain how you are figuing out how many rooms there are? thanks ----------------------------------- zylum Sat Feb 21, 2004 7:40 pm ----------------------------------- 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... %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 ----------------------------------- Andy Sun Feb 22, 2004 1:53 pm ----------------------------------- wow that is so much longer... for my way, i just draw fill then count how many different color there are ----------------------------------- zylum Sun Feb 22, 2004 8:23 pm ----------------------------------- 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 ----------------------------------- AsianSensation Tue Feb 24, 2004 7:52 am ----------------------------------- or since this is almost a standard maze question, we could all just use recursion and forget about whatdotcolor? ----------------------------------- zylum Tue Feb 24, 2004 3:57 pm ----------------------------------- good idea :D