Ruudukko

import json
import time
 
n = int(input(''))
 
table = []
for y in range(n):
    table.append(input(''))
 
position_values = [[None for y in range(n)] for x in range(n)]
 
class Container():
    def __init__(self, data):
        self.data = data
 
    def increment(self):
        self.data = [
            (a + 1, b + 1)
            for a, b in self.data
        ]
 
    def compress(self):
        sorted_data = sorted(self.data)
 
        compressed_data = []
 
        i = 0
        while i < len(sorted_data):
            cur_min = sorted_data[i][0]
            cur_max = sorted_data[i][1]
            while True:
                i += 1
                if i == len(sorted_data):
                    break
 
                this_min = sorted_data[i][0]
                this_max = sorted_data[i][1]
                if this_min - 1 > cur_max:
                    break
                cur_max = max(cur_max, this_max)
 
            compressed_data.append((cur_min, cur_max))
 
        self.data = compressed_data
 
        pass
 
    def value(self):
        self.compress()
        value = list(set(sum([list(range(a, b + 1)) for a, b in self.data], [])))
        # print('value', value)
        return value
 
    @classmethod
    def from_one(cls, other, this_adds):
        item = cls(other.data)
        if this_adds:
            item.increment()
        return item
 
    @classmethod
    def from_two(cls, other1, other2, this_adds):
        item = cls(other1.data + other2.data)
        item.compress()
        if this_adds:
            item.increment()
        return item
 
 
 
for x in range(n):
    for y in range(n):
        table_value = table[x][y]
        new_container = None
        if x == 0 and y == 0:
            new_container = Container([(0, 0)]) if table_value == '.' else Container([(1, 1)])
        elif y == 0:
            new_container = Container.from_one(
                position_values[x - 1][y],
                table_value == 'o'
            )
        elif x == 0:
            new_container = Container.from_one(
                position_values[x][y - 1],
                table_value == 'o'
            )
        else:
            new_container = Container.from_two(
                position_values[x][y - 1],
                position_values[x - 1][y],
                table_value == 'o'
            )
 
        position_values[x][y] = new_container
 
 
# Vastaukset:
# 280
# 564
 
 
solution: Container = position_values[n-1][n-1]
print(len(solution.value()))

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED