-----------------------------------

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