Оптимизация алгоритмов кода(сортировка, работа с двумерными списками)

[Rjugo]

Доброго времени суток, уважаемые форумчане, несколько дней мучался над программой, сейчас она работает ВСЕГО ЛИШЬ на на 0,015 секунды дольше чем должна, голова уже не варит от слова совсем, так что нужна помощь знающих людей, пожалуйста, прооптимизируйте мой горе код на сколько это возможно, я буду крайне Вам признателен

за ранее ОГРОМНОЕ СПАСИБО!
Задача с Timus 1287 “Каналы на марсе” (СМ прикрепленный файл)


Один из районов поверхности Марса покрыт идеальной сеткой каналов. Они делят поверхность на одинаковые квадратные клетки (кривизной поверхности мы здесь пренебрегаем). Сам район представляет собой идеальный квадрат, каждая сторона которого разбита на N клеток.
Как показали исследования археологической экспедиции, покрытый каналами район Марса занимала древняя страна под названием Йатик. Жители Йатика выращивали специальный злак — сир — который составлял основу их метаболизма. Сир бывает двух сортов — крупно- и мелкозернистый. Собственно, закат империи Йатика начался после гражданской войны между любителями этих сортов. До последнего времени, однако, не было установлено, какая из партий победила в этой кровопролитной войне. Результаты последней экспедиции на Марс позволяют надеяться на разгадку этой исторической тайны. Ученым удалось установить, сир какого сорта был последним высеян в той или иной клетке Йатика. Поскольку, по стародавней традиции, сир высевали в последовательности клеток (параллельные сторонам света, или идущие под углом 45° к ним), можно предположить, что сторонники победившей партии делали наиболее длинные посевы.
Исходные данные
В первой строке входа содержится единственное число N — размер квадрата (1 ≤ N ≤ 1400). Затем следуют N строк, каждая из которых состоит ровно из N символов. Буква “s” в i-й строке и j-м столбце означает, что в соответствующей клетке квадрата последним был высеян мелкозернистый сир, буква “S” означает, что последним был высеян крупнозернистый сир. Можно считать, что жители данного района не выращивали ничего кроме сира, и в каждой клетке района был засеян сир одного из этих двух сортов.
Результат
В первую строку нужно записать символ “s”, если в кровопролитной войне победила партия любитетей мелкозернистого сира, и символ “S”, если крупнозернистого. Если победителя определить невозможно, то первая строка должна содержать единственный символ “?”. Во второй строке должно быть записано целое число — максимальная длина посева сира одного сорта.


Программный код (С комментариями для понимания):

def tra(mat):  # ФУНКЦИЯ, которая транспонирует исходную матрицу
    tm = list()
    for i in range(len(mat)):
        tm.append(list(len(mat[i]) * '0'))
    for i in range(len(mat)):
        for j in range(len(mat)):
            tm[j][i] = mat[i][j]  # Поворот матрицы на бок, при помощи замены x и y местами
    return tm


def scm(mat,lt):  # ФУНКЦИЯ, которая находит самые длинные неприрывные цепочки (среди строк передаваемой в качестве матрицы) из букв, возвращет букву, из которой состоит саммая длинная цепочка и колличесвто этой буквы в цепочке или знак "?" если в строчке равное колличесвто букв S и s (второй аргумент всегда 0, углубляться почему это так не буду)
    fug = list()
    for i in range(len(mat)):
        fg = list()
        arg = 1
        a = mat[i][0]  # начальный элемент строки
        for i1 in range(1, len(mat[i])):
            if mat[i][i1] == a:
                arg += 1  # добавляем +1 если совпал проверяемый элемент
            else:
                fg.append([arg, a])  # конец подстрочки из однаковых элементов
                arg = 1
                a = mat[i][i1]
        fg.append([arg, a])  # запись последнего элемента
        fg.sort()  # сортировка по возрастанию
        if len(fg) > 1:
            gh = fg[-1]
            for i in range(len(fg) - 2, -1, -1):
                if fg[i][0] == gh[0]:
                    if fg[i][1] == gh[1]:
                        pass
                    else:
                        fug.append([fg[i][0], "?"])  # две максимально длинных подстроки совпадают длиной
                        break
                else:
                    fug.append(fg[-1])  # максимальная подстрока самая большая и не имеет аналогов
                    break
        else:
            fug.append(fg[0])  # что-то пошло не по плану
    if lt == 1:
        return fug  # если lt=1, то просто выводим максимумы строк
    elif lt == 0:
        fug.sort()
        gh = fug[-1]
        fg = list()
        f = False
        for i in range(len(fug) - 2, -1, -1):
            if fug[i][0] == gh[0]:
                if fug[i][1] == gh[1]:
                    pass
                else:
                    return [fug[i][0], "?"]  # два максимума под строк совпадают
                    f = True
                    break
            else:
                return fug[-1]  # максимум строки всего 1
                f = True
                break
        if not f:
            return fug[-1]  # если ничего не нашло

N = int(input())
POLE = []
ALL_0 = []
ALL_1 = []
ALL_2 = []
OTVET = []
for i in range(N):
    POLE.append(list(input()))
if N == 1:  # частный случай, когда размер поля 1 на 1 то сразу можем сказать ответ
    print(POLE[0][0])
    print(1)
else:
    l = len(POLE)  # находим все диагонали
    b = l * 2 - 1  # находим все диагонали
    ALL_DIAG = [[] for _ in range(b * 2)]
    м
    for i in range(l):  # находим все диагонали
        for j in range(l):  # находим все диагонали
            ALL_DIAG[i + j].append(POLE[j][i])  # находим все диагонали
            ALL_DIAG[i + j + b].append(POLE[~j][i])  # находим все диагонали
    ALL_0.append(
        ALL_DIAG)  # (МАТРИЦА ДЛЯ ВСЕГО) запихиваем все диагонали  # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО это матрица где хранятся все диагонали столбцы и строчки)
    ALL_1 = [c for d in ALL_0 for c in
             d]  # очищаем матрицу со всеми строками столбцами диагоналями от лишних скобок т.е.[[[a],[b]]] = [[a],[b]]
    for i in range(N):  # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
        ALL_1.append(POLE[i])  # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
    ALL_2 = (tra(POLE))  # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
    for i in range(N):  # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
        ALL_1.append(ALL_2[i])  # запихиваем все строчки в (МАТРИЦА ДЛЯ ВСЕГО)
    OTVET.append(scm(ALL_1, 0))  # вызываем функцию scm,  которая сама находит ответ на задачу(МАТРИЦА ДЛЯ ВСЕГО)
    print(OTVET[0][1])
    print(OTVET[0][0])

    fug = list()
    for i in range(len(mat)):
        fg = list()
        arg = 1
        a = mat[i][0]  # начальный элемент строки
        for i1 in range(1, len(mat[i])):
            if mat[i][i1] == a:
                arg += 1  # добавляем +1 если совпал проверяемый элемент
            else:
                fg.append([arg, a])  # конец подстрочки из однаковых элементов
                arg = 1
                a = mat[i][i1]
        fg.append([arg, a])  # запись последнего элемента
        fg.sort()  # сортировка по возрастанию
        if len(fg) > 1:
            gh = fg[-1]
            for i in range(len(fg) - 2, -1, -1):
                if fg[i][0] == gh[0]:
                    if fg[i][1] == gh[1]:
                        pass
                    else:
                        fug.append([fg[i][0], "?"])  # две максимально длинных подстроки совпадают длиной
                        break
                else:
                    fug.append(fg[-1])  # максимальная подстрока самая большая и не имеет аналогов
                    break
        else:
            fug.append(fg[0])  # что-то пошло не по плану
    if lt == 1:
        return fug  # если lt=1, то просто выводим максимумы строк
    elif lt == 0:
        fug.sort()
        gh = fug[-1]
        fg = list()
        f = False
        for i in range(len(fug) - 2, -1, -1):
            if fug[i][0] == gh[0]:
                if fug[i][1] == gh[1]:
                    pass
                else:
                    return [fug[i][0], "?"]  # два максимума под строк совпадают
                    f = True
                    break
            else:
                return fug[-1]  # максимум строки всего 1
                f = True
                break
        if not f:
            return fug[-1]  # если ничего не нашло
N = int(input())
POLE = []
ALL_0 = []
ALL_1 = []
ALL_2 = []
OTVET = []
for i in range(N):
    POLE.append(list(input()))
if N == 1:  # частный случай, когда размер поля 1 на 1 то сразу можем сказать ответ
    print(POLE[0][0])
    print(1)
else:
    l = len(POLE)  # находим все диагонали
    b = l * 2 - 1  # находим все диагонали
    ALL_DIAG = [[] for _ in range(b * 2)]
    м
    for i in range(l):  # находим все диагонали
        for j in range(l):  # находим все диагонали
            ALL_DIAG[i + j].append(POLE[j][i])  # находим все диагонали
            ALL_DIAG[i + j + b].append(POLE[~j][i])  # находим все диагонали
    ALL_0.append(
        ALL_DIAG)  # (МАТРИЦА ДЛЯ ВСЕГО) запихиваем все диагонали  # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО это матрица где хранятся все диагонали столбцы и строчки)
    ALL_1 = [c for d in ALL_0 for c in
             d]  # очищаем матрицу со всеми строками столбцами диагоналями от лишних скобок т.е.[[[a],[b]]] = [[a],[b]]
    for i in range(N):  # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
        ALL_1.append(POLE[i])  # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
    ALL_2 = (tra(POLE))  # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
    for i in range(N):  # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
        ALL_1.append(ALL_2[i])  # запихиваем все строчки в (МАТРИЦА ДЛЯ ВСЕГО)
    OTVET.append(scm(ALL_1, 0))  # вызываем функцию scm,  которая сама находит ответ на задачу(МАТРИЦА ДЛЯ ВСЕГО)
    print(OTVET[0][1])
    print(OTVET[0][0])