Niitty

import random
import time
import sys
sys.setrecursionlimit(15000)


n = int(input())
rows = [[l for l in input()] for _ in range(n)]#[["ABCDEFGHIJKLMNOPQRSTUVWXYZ"[random.randint(0, 25)] for _ in range(n)] for _ in range(n)]#[["A", "A", "B"], ["A", "B", "A"], ["A", "A", "A"]]### ###

species_to_number = {}
for y in range(len(rows)):
    for x in range(len(rows)):
        if(rows[y][x] not in species_to_number.keys()):
            species_to_number[rows[y][x]] = len(species_to_number.keys())+1
        rows[y][x] = species_to_number[rows[y][x]]

    #print(" ".join(map(str, rows[y])))


existing_species_mask = int("0b"+"1"*len(species_to_number.keys()), 2)


#[print(" ".join(map(str, rows[i]))) for i in range(n)]

#start_time = time.time()

fitting_fences = 0


found_species_per_row = []
for row in rows:
    row_mask = 0
    for item in row:
        row_mask = row_mask | (2**item)>>1

    found_species_per_row.append(row_mask)


for y1 in range(len(rows)):

    for y2 in range(len(rows)-1, y1-1, -1):

        mask = 0
        for row_mask in found_species_per_row[y1:y2+1]:
            mask = mask | row_mask

            if(mask == existing_species_mask):
                break
        else:
            break

        columns = [list(e) for e in zip(*rows[y1:y2+1][::-1])]
        found_species_per_column = []
        for column in columns:
            column_mask = 0
            for item in column:
                column_mask = column_mask | (2**item)>>1

            found_species_per_column.append(column_mask)


        for x1 in range(len(columns)):
            for x2 in range(len(columns)-1, x1-1, -1):
                mask = 0
                for column_mask in found_species_per_column[x1:x2+1]:
                    mask = mask | column_mask

                    if(mask == existing_species_mask):
                        break
                else:
                    break

                fitting_fences += 1


print(fitting_fences)

#print(time.time()-start_time)

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 7

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 13

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 14

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 4, 5, 6

Verdict: ACCEPTED

Test 18

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 6

Verdict: TIME LIMIT EXCEEDED