Попытка выяснить самый длинный алгоритм пути python

Я пытаюсь создать скрипт Python, который дает мне самый длинный повторяющийся символ в заданной матрице (по горизонтали и вертикали).

Пример:

У меня есть эта матрица:

afaaf
rbaca
rlaff

При подаче этой матрицы на вход должно получиться: a 3

Вы можете видеть, что 3-й столбец матрицы заполнен буквами «а», а также это самый повторяющийся символ в матрице.

Что у меня есть:

#!/bin/python2.7

#Longest string in matrix

#Given a matrix filled with letters. Find the longest string, containing only the same letter, which can be obtained by starting
#with any position and then moving horizontally and vertically (each cell can be visited no more than 1 time).


# Settings here
# -------------
string_matrix = """
afaaf
rbaca
rlaff
"""

pos = (0,0)
# -------------

import pdb
import time
import collections
from collections import defaultdict
import re


rows = 0
columns = 0
matrix = []
matrix2 = []
counter = 0
res_l = []
i = 0
c = ''

# if matrix2 is full of 1's, stop
def stop():
    for i in range(0, rows):
        for j in range(0, columns):
            if matrix2[i][j] == 0:
                return False
    return True

# checks the points, and returns the most repeated char and length
def check_points(points1, points2):
    r = []

    r.append(-1)
    r.append('')

    # create strings from matrix
    s1 = ''
    s2 = ''


    for point in points1:
        s1 += matrix[point[0]][point[1]]

    for point in points2:
        s2 += matrix[point[0]][point[1]]

    rr = {}

    for c in s1:
        rr[c] = 0

    for c in s2:
        rr[c] = 0

    for i in range(0, len(s1)):
        k = 1
        for j in range(i+1, len(s1)):
            if s1[i] == s1[j]:
                k += 1
            else:
                break
            if k > rr[s1[i]]:
                rr[s1[i]] = k


    for i in range(0, len(s2)):
        k = 1
        for j in range(i+1, len(s2)):
            if s2[i] == s2[j]:
                k += 1
            else:
                break
            if k > rr[s2[i]]:
                rr[s2[i]] = k


    m = -1
    c = ''
    for key,value in rr.iteritems():
        if value > m:
            m = value
            c = key

    return m, c


# Depth-first search, recursive
def search(pos):
    global res_l
    global matrix2
    global c

    counter = 0

    x = pos[0]
    y = pos[1]

    c = matrix[x][y]

    # base clause
    # when matrix2 is all checked
    if stop():
        return counter, c



    points1 = []
    points2 = []
    allpoints = []

    for i in range(0, columns):
            if matrix2[x][i] != 1:
                points1.append([x, i])
                allpoints.append([x, i])


    for i in range(0, rows):
            if matrix2[i][x] != 1:
                points2.append([i, x])
                allpoints.append([i, x])





    r = check_points(points1, points2)


    if r[0] > counter:
        counter = r[0]
        c = r[1]

    matrix2[x][y] = 1


    for point in allpoints:
        rr = search(point)
        if rr[0] > counter:
            counter = int(rr[0])
            c = rr[1]
            #print 'c: ' + str(c) + ' - k: ' + str(counter)



    return counter, c

def main():
    # create the matrix from string
    string_matrix_l = string_matrix.strip()
    splited = string_matrix_l.split('\n')


    global rows
    global columns
    global matrix
    global matrix2

    rows = len(splited)
    columns = len(splited[1])



    # initialize matrixes with 0
    matrix = [[0 for x in range(columns)] for x in range(rows)]
    matrix2 = [[0 for x in range(columns)] for x in range(rows)]


    # string to matrix
    i = 0
    for s in splited:
        s = s.strip()
        if s == '':
            continue

        j = 0

        for c in s:
            try:## Heading ##
                matrix[i][j] = c
                #print 'ok: ' + str(i) + ' ' + str(j) + ' ' +  c
            except:
                print 'fail: index out of range matrix[' + str(i) + '][' + str(j)+'] ' + c
            j = j + 1

        i = i + 1


    # print some info
    print 'Given matrix: ' + str(matrix) + '\n'
    print 'Start position: ' + str(pos)
    print 'Start character: ' + str(matrix[pos[0]][pos[1]])

    # get the result
    res = search(pos)
    print '-------------------------------------'
    print '\nChar: ' + str(res[1]) + '\nLength: ' + str(res[0])


if __name__ == "__main__":
    main()

Это мой исходный код. Пример, приведенный выше, также используется в исходном коде. Полученный результат: r 2, что неверно... снова должно быть a 3.

Имеет 4 функции: основная, поиск, остановка и контрольные_точки.

• main инициализирует вещи,
• search — это моя рекурсивная функция, которая принимает один параметр (начальную точку) и должна рекурсивно проверять самую длинную строку. У меня есть другая матрица той же длины, что и исходная, которая состоит только из 1 и 0. 1 означает, что позиция была посещена, 0 - нет. Функция поиска устанавливает 1 в правильном положении после того, как определенная позиция была обработана функцией поиска.
• stop проверяет, заполнена ли матрица2 единицами, в этом случае вся матрица была проанализирована
• check_points принимает 2 параметра, 2 списка точек и возвращает наиболее повторяющийся символ и его длину для этих точек.

Что не работает:

Большую часть времени в результате я получаю неправильный символ, даже если иногда счет может быть правильным. Иногда работает по горизонтали, иногда нет. Я уверен, что делаю что-то не так, но... уже более 1 недели, как я пытаюсь понять, как это сделать. Задал еще один вопрос здесь, в stackoverflow, немного продвинулся, но ... все еще застрял.

Любое предложение приветствуется.