CSES - Datatähti 2016 alku - Results
Submission details
Task:Tontti
Sender:AnttiR
Submission time:2015-09-30 22:05:50 +0300
Language:Python2
Status:READY
Result:14
Feedback
groupverdictscore
#1ACCEPTED14
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.07 s1details
#2ACCEPTED0.33 s1details
#3ACCEPTED0.10 s1details
#4ACCEPTED0.07 s1details
#5ACCEPTED0.08 s1details
#6--2details
#7--2details
#8--2details
#9--2details
#10--2details
#110.57 s3details
#12--3details
#130.64 s3details
#140.66 s3details
#150.64 s3details

Code

trees = []
height,width,wantedTrees = [int(x) for x in raw_input().split(" ")]
# Last tiles you can go to in each direction
limits = width-1, height-1
# Find trees from imput and place them to an list.
for y in range(0,height):
inputRow = raw_input()
for x in range(0, len(inputRow)):
if inputRow[x] == '*':
trees.append((x,y))
# Find all possible squares, that are as small as possible.
foundRectangles = []
shorter_smaller = 0
shorter_higher = 0
longer_higher = 0
longer_smaller = 0
for index_1 in range(0,len(trees)):
for index_2 in range(index_1,len(trees)):
tree_1 = trees[index_1]
tree_2 = trees[index_2]
longer = 0
if abs(tree_1[0]-tree_2[0]) < abs(tree_1[1]-tree_2[1]):
longer = 1
shorter = (longer + 1) % 2
if tree_1[shorter] >= tree_2[shorter]:
shorter_higher = tree_1[shorter]
shorter_smaller = tree_2[shorter]
else:
shorter_higher = tree_2[shorter]
shorter_smaller = tree_1[shorter]
if tree_1[longer] >= tree_2[longer]:
longer_higher = tree_1[longer]
longer_smaller = tree_2[longer]
else:
longer_higher = tree_2[longer]
longer_smaller = tree_1[longer]
side = longer_higher - longer_smaller
max_distance = side - (shorter_higher - shorter_smaller)
# Shorter is the axis with varying values.
# Max distance is the max variance from the default position.
# Longer is the axis that has longer distance beetween the values of the two points.
# Longer determines the size of the rectangle.
all_positions = list(range(max(0, max_distance - shorter_smaller), min(max_distance, (limits[shorter]) - shorter_higher)+1))
# If it is impossible to construct a square with those two trees inside, just continue.
if len(all_positions)==0:
continue
# Find where a new tree enters or leaves the area.
modifyTrees = dict([(i, 0) for i in all_positions])
for tree in trees:
if tree[longer] < longer_smaller or tree[longer] > longer_higher:
continue
tree_pos = tree[shorter]
if tree_pos < shorter_smaller-max_distance+all_positions[0] or tree_pos > shorter_higher+all_positions[-1]:
continue
# The tree is somewhere in the vicinity of our rectangle. Let's find it!
if tree_pos < shorter_smaller - max_distance + all_positions[-1]:
modifyTrees[tree_pos + max_distance - shorter_smaller + 1] -= 1
modifyTrees[all_positions[0]] += 1
elif tree_pos > shorter_higher+all_positions[0]:
modifyTrees[tree_pos - shorter_higher] += 1
else:
modifyTrees[all_positions[0]] += 1
# Find areas with the correct amount of trees.
trees_in_area = 0
for positionModifier in all_positions:
trees_in_area+=modifyTrees[positionModifier]
if trees_in_area == wantedTrees:
if longer == 0:
rectangle = (longer_smaller,shorter_smaller-max_distance+positionModifier,side)
else:
rectangle = (shorter_smaller-max_distance+positionModifier,longer_smaller,side)
if rectangle not in foundRectangles:
foundRectangles.append(rectangle)
# Now, for every small rectangle, try to make it larger in each direction.
lFR = []
def tryLargerRectangles(rectangle):
side = rectangle[2]+1
recX=rectangle[0]
recY=rectangle[1]
for dxy in [(-1,-1),(-1,0),(0,-1),(0,0)]:
newX = recX
newY = recY
newRecX=recX+dxy[0]
newRecY=recY+dxy[1]
if dxy[0]==0:
newX+=side
else:
newX-=1
if dxy[1]==0:
newY+=side
else:
newY-=1
if newX < 0 or newX > limits[0] or newY < 0 or newY > limits[1]:
continue
conflict = False
for tree in trees:
tree_x = tree[0]
tree_y = tree[1]
if (tree_x == newX and tree_y >= newRecY and tree_y <= newRecY+side) or (tree_y == newY and tree_x >= newRecX and tree_x <= newRecX+side):
conflict = True
break
if not conflict:
newRec = (newRecX,newRecY,side)
if newRec not in lFR:
lFR.append(newRec)
tryLargerRectangles(newRec)
for rectangle in foundRectangles:
tryLargerRectangles(rectangle)
print len(lFR)+len(foundRectangles)

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10 10 1
......*...
.......*..
*..*....*.
*....*....
...

correct output
94

user output
94

Test 2

Group: 1

Verdict: ACCEPTED

input
10 10 5
**********
**********
**********
**********
...

correct output
0

user output
0

Test 3

Group: 1

Verdict: ACCEPTED

input
10 10 10
**...*...*
*..*.**.*.
...**.*..*
*...**.*..
...

correct output
4

user output
4

Test 4

Group: 1

Verdict: ACCEPTED

input
10 10 5
****......
*.*.**..**
....*.*..*
...*.***..
...

correct output
16

user output
16

Test 5

Group: 1

Verdict: ACCEPTED

input
10 10 2
**.***..*.
...*.*....
.***.*...*
***.***..*
...

correct output
30

user output
30

Test 6

Group: 2

Verdict:

input
500 500 1
.................................

correct output
9552040

user output
(empty)

Test 7

Group: 2

Verdict:

input
500 500 5
.................................

correct output
1536063

user output
(empty)

Test 8

Group: 2

Verdict:

input
500 500 25000
**...*...**..*.*..*.**.*..*.*....

correct output
288

user output
(empty)

Test 9

Group: 2

Verdict:

input
500 500 12500
**.**.*..*...*.**...*.***........

correct output
786

user output
(empty)

Test 10

Group: 2

Verdict:

input
500 500 5000
.*.*.**..*.*.**.**..*..**...*....

correct output
1763

user output
(empty)

Test 11

Group: 3

Verdict:

input
2000 2000 1
.................................

correct output
489611392

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 131, in <module>
    tryLargerRectangles(rectangle)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(ne...

Test 12

Group: 3

Verdict:

input
2000 2000 5
.................................

correct output
120725884

user output
(empty)

Test 13

Group: 3

Verdict:

input
2000 2000 400000
..*..**.**.**.*.***...**.*..**...

correct output
1849

user output
(empty)

Test 14

Group: 3

Verdict:

input
2000 2000 200000
***.*....*.*..*....**..*..*.*....

correct output
2665

user output
(empty)

Test 15

Group: 3

Verdict:

input
2000 2000 80000
**.**...*.***.**....**.*....*....

correct output
5587

user output
(empty)