어떤 임의의 두 지점을 연결하는 길이 하나뿐이라는 조건 때문에 내부 구조는 사이클이 없는 그래프가 되어야 합니다. 이러한 구조는 트리 또는 트리들의 집합인 포리스트밖에 없습니다.

엄밀히 따지면 포리스트를 고려해야 되기는 한데, 결국 트리에 대한 해법을 여러 번 적용하는 것이므로 트리에 대한 해법만을 생각해 봅시다.

어떤 트리 내부에서 가장 거리가 먼 두 지점을 찾는 방법은 다음과 같습니다.
1. 어떤 임의의 노드 a로부터 가장 거리가 먼 b라는 지점을 찾습니다.
2. 다시 b로부터 가장 거리가 먼 c라는 지점을 찾습니다.
3. b-c 사이가 가장 거리가 먼 지점이 됩니다.

이것을 증명하는 방법은 다음과 같습니다.

가정) b와 c를 연결하는 path(이하 b-c)보다 더 긴 path P가 존재합니다.
먼저 b는 반드시 트리의 leaf 노드가 됩니다. 이는 자명합니다.

1. P와 a-b 사이에 교점이 있는 경우
  P의 한 끝점과 a를 연결하는 path가 반드시 a-b보다 길게 됩니다. 이것은 b가 a로부터 가장 먼 지점이라는 가정에 모순입니다.
2. P와 a-b 사이에 교점이 없는 경우
  그래프는 트리 형태이므로 path P로부터 a로 이어지는 경로가 반드시 존재합니다. 즉, 
  (Path P 위의 점 중에서 A로부터 가장 가까운 중간점) - .... - a - (중간중간에 가지) - b 형태여야 합니다.
  그런데 b가 a로부터 가장 먼 지점이므로 이때 P의 양쪽 끝(P1, P2)으로부터 a로의 거리는 (a-b)보다 짧아야 합니다.
  len(a-b) > len(P1-a) + len(a-P2) > len(P1-P2)

  다시 말해서 P의 길이는 (a-b의 길이)보다는 반드시 짧습니다.

  그런데 이 경우, P1 또는 P2를 C로 하여 (B-C)를 연결하는 것이 P보다 반드시 길게 됩니다
  len(a-b) + len(P1-a) > len(P1-P2)
  len(a-b) + len(P2-a) > len(P1-P2)

  따라서 이러한 P는 존재할 수 없습니다. 

그러므로 (B-C)가 트리상에서 가장 긴 Path가 됩니다.

아래 코드는 포리스트는 고려하지 않고 내부가 트리 형태로 이어져 있다고 보았을 경우에 해당합니다.

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

def get_farthest(map, start_pos):
    n = len(map)
    m = len(map[0])
    dir = [(-1, 0), (1, 0), (0, 1), (0, -1)]    

    visited = set([start_pos])
    queue = Queue();    

    queue.enqueue([0, start_pos])            
    last = ''

    while not queue.isEmpty():    
        last = queue.dequeue()
        dist, here = last 

        candidates = [ (here[0]+dy, here[1]+dx) for (dx,dy) in dir ]        

        for next_pos in candidates:
            ny, nx = next_pos
            if ny < 0 or ny >= n or nx < 0 or nx >= m:
                continue
            elif map[ny][nx] != '.':
                continue
            elif next_pos not in visited:
                visited.add(next_pos)
                queue.enqueue( [dist + 1, next_pos] )            
    return last

def find_empty_place(map):
    n = len(map)
    m = len(map[0])
    for i in range(0, n):
        for j in range(0, m):
            if map[i][j] != '#':
                return (i, j)
    return ''

def labyrinth(map):    
    pos1 = get_farthest(map, find_empty_place(map))[1]
    dist = get_farthest(map, pos1)[0]
    return dist

def main():
    testcases = int(input())
    for test in range(0, testcases):
        m, n = list(map(lambda x:int(x), input().split()))
        mapData = []

        for i in range(0, n):
            mapData.append(input())

        answer = labyrinth(mapData)

        print("Maximum rope length is %d." % answer)

main()

[문제이해]

각 갈림길(과 막다른 길)을 정점으로 보면, 싸이클이 없으므로

갈림길 사이의 경로를 간선, 그 길이를 가중치로 하는 4-ary 트리가 된다.

이 트리에서 같은 노드를 두 번 이상 방문하지 않는 최장경로의 길이를 구해야 한다.

[주의할 점]

1) 미로 안에 서로 연결되지 않은 둘 이상의 길(트리)이 있을 수 있다.

이 때는 트리 갯수만큼 각각 탐색해서 답을 갱신해야 한다.

.

2) 문제의 가정에 의해,

최장경로(=문제의 답)는 반드시 막다른 길에서 시작해서 막다른 길에서 끝난다.

(굳이 증명하지 않더라도 조금만 생각해 보면 알 수 있다.)

만약 어떤 막다른 길((i, j) 라고 하자)에서부터 탐색을 시작한다면(저도 처음에는 이렇게 풀었습니다만..),

(i, j)가 최장경로에 포함되지 않는 경우도 고려해야 한다.

즉 모든 막다른 길을 시작점 혹은 끝점으로 해서 탐색해야 한다.

[풀이]

임의의 정점을 루트로 하는 트리 T를 만든다.

트리 T 에 대해서,

노드 u, w를 잇는 간선의 가중치를 W(v, w),

노드 u를 루트로 하는 서브트리를 Tu

라고 하자.

Tu에서 u에서 leaf에 이르는 경로 중 가장 긴 경로의 길이를 L(u), 두 번째를 L2(u)라 할 때,

(두 경로는 교집합이 없다)

Tu 안에서 u를 지나는 최장거리는

M(u) = L(u) + L2(u)

이다(u를 중심으로 L(), L2()는 단방향, M()은 양방향).

=> 모든 M() 값 중 최대값이 "가장 긴 로프 길이"가 된다(아래 [증명] 참조)

구현을 위해 식을 조금 정리하자.

u의 자식이 c, c2, c3, c4이고

L(u) 에 속한 u의 자식이 c, L2(u)에 속한 u의 자식이 c2라면(c1 != c2)

L(u) = max(
    L(c) + W(c, u),
    L(c2) + W(c2, u),
    L(c3) + W(c3, u),
    L(c4 + W(c4, u)
    )
    = L(c) + W(c, u)

L()에 대한 점화식이다.

M(u) = L(u) + L2(u) = L(c) + W(c, u) + W(u, c2) + L(c2)

M() 역시 L()에 관한 식이다. L2()는 c2를 던져주고 어딘가로 사라져 버린다.

[수행시간]

재귀적으로 구현되어 있지만 사실은 모든 노드를 한 번씩만 방문한다.

2차원 배열로 치면 각 칸을 최대 한 번씩 지나므로 O(CR)이고,

그래프에서 본다면 모든 정점과 간선을 한 번씩 지나므로

O(V+E) = O(V + (V-1)) = O(2V) = O(V)

이다.

[증명-무엇이 문제인가?]

M(v)는 Tv 안에서 v를 지나는 최장거리이다. v를 안 지나는 경우는?

.

앞에서 임의의 노드를 루트로 트리 T를 만들었다.

그렇다면 하나의 미로에 대해 서로 다른 T1, T2, T3, ... 이 존재할 수 있는데,

트리 T에 적용한 위의 풀이가 "만들 수 있는 모든 경로를 포함한다" 를 보이지 않으면

모든 T1, T2, T3, ... 을 만들어서 적용해야 한다.

[증명]

트리 T의 루트 노드가 root이고, 그 자식이 c1, c2라고 할 때(최대 넷이지만 여기서는 크게 관계없다),

1) 최장경로(=문제의 답)가 root를 지난다면:

답은 M(root)이다.

2) 최장경로가 root를 지나지 않는다면:

root를 지나지 않고 c1과 c2를 연결하는 경로는 없다. 따라서 최장경로는

2-1) Tc1 에 속한 노드만 지나거나,

2-2) Tc2 에 속한 노드만 지난다.

2-1) 과 2-2) 에 1) 과 2) 를 재귀적으로 적용하면

위의 풀이는 만들 수 있는 모든 경로를 포함한다.

따라서 트리 T에 대해, 모든 노드의 M() 중 최대값이 답이 된다.

구현은 트리 만들고, L() 구하고, M() 구하면 되는데...

이전 코드에 얹어서 하느라 좀 기형적으로 변했습니다.

import numpy as np

class Maze:
    def __init__(self, arr, R, C):
        self.arr = np.array(arr)
        self.R, self.C = R, C

    # 인접 4방향에서 빈 칸(.)을 찾는다.
    def pathsfrom(self, idx):
        paths = []
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            r, c = idx[0] + dr, idx[1] + dc
            if 0 <= r < self.R and 0 <= c < self.C and self.arr[r, c] == '.':
                paths.append((r, c))

        return paths

    # 출발점을 정한다.
    def startfrom(self):
        for i in range(self.R):
            for j in range(self.C):
                if self.arr[i, j] == '.':
                    return (i, j)

        return None

    # 가장 긴 로프 길이를 구한다.
    def longest_rope(self):
        ropemax = 0
        startpos = self.startfrom()
        while startpos:
            solutions = list()
            solutions.append(self.oneway(startpos, solutions))
            ropemax = max(ropemax, *solutions)
            startpos = self.startfrom()

        return ropemax

    # self.arr[idx]를 루트 노드로서 경유할 때(양방향) 최장거리를 twoway에 저장하고,
    # 막다른 길에서 self.arr[idx]까지(단방향) 최장거리를 리턴한다. 
    def oneway(self, idx, twoway):
        self.arr[idx] = 'X' # 왔던 길 표시
        ropelen = 0
        paths = self.pathsfrom(idx)
        while len(paths) == 1: # 쭉 간다.
            idx = paths[0]
            self.arr[idx] = 'X'
            ropelen += 1
            paths = self.pathsfrom(idx)

        if len(paths) > 1: # 갈림길
            pathslen = [self.oneway(path, twoway) for path in paths]
            pathslen.sort()
            twoway.append(pathslen[-1] + 2 + pathslen[-2])
            ropelen += 1 + pathslen[-1]
            return ropelen
        else: # 막다른 길
            twoway.append(ropelen)
            return ropelen


inp = input_string.split('\n')
n_test = int(inp.pop(0))
for i in range(n_test):
    C, R = map(int, inp.pop(0).split())
    arr = []
    for r in range(R):
        arr.append(list(inp.pop(0)))

    maze = Maze(arr, R, C)
    print("Maximum rope length is {}.".format(maze.longest_rope()))

Eight Queen과 비슷한 문제로 보입니다. 비슷한 방법으로 풀었습니다.

파이썬입니다.

# -*- coding: utf-8 -*-
import unittest

class Square:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.isRock = False

    def __str__(self):
        return "(%s,%s)\t" % (self.x, self.y)


class Matrix:
    direction = [
        (0,-1),
        (0,+1),
        (-1,0),
        (+1,0),
    ]
    def __init__(self, src):
        src = src.strip()
        self.map = []
        for y, line in enumerate(src.split("\n")):
            line = line.strip()
            cols = []
            for x, item in enumerate(list(line)):
                square = Square(x,y)
                if item == '#':
                    square.isRock = True
                cols.append(square)
            self.map.append(cols)

    def getStartSquare(self):
        for x in range(len(self.map[0])):
            for y in range(len(self.map)):
                square = self.map[y][x]
                if not square.isRock:
                    return square
        return None

    def run(self):
        startSquare = self.getStartSquare()
        if not startSquare: return 0
        all_path = self.start(startSquare, [])
        return max(map(len, all_path)) -1

    def getNextSquares(self, square, found=[]):
        result = []
        for dx, dy in self.direction:
            next = self.getSquare(square.x+dx, square.y+dy)
            if next and not next.isRock and next not in found:
                result.append(next)
        return result

    def getSquare(self, x, y):
        if 0 <= x < len(self.map[0]) and 0 <= y < len(self.map):
            return self.map[y][x]
        else:
            return None

    def start(self, square, found, result=[]):
        found = list(found)
        found.append(square)

        squares = []
        while True:
            squares = self.getNextSquares(square, found)
            if len(squares) != 1: break
            found.append(squares[0])
            square = squares[0]
            #print square
        if not squares: 
            result.append(found)
        else:
            for next in squares:
                self.start(next, tuple(found))
        return result


class MyTest(unittest.TestCase):
    def test1(self):
        src = """
###
#.#
###
        """

        matrix = Matrix(src)
        self.assertEquals(0, matrix.run())

    def test2(self):
        src = """
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######
        """

        matrix = Matrix(src)
        self.assertEquals(8, matrix.run())

    def test3(self):
        src = """
#######
#.#.#.#
#.#.#.#
#.#.#.#
#.#.#.#
#.....#
#######
        """

        matrix = Matrix(src)
        self.assertEquals(12, matrix.run())

    def test4(self):
        src = []
        src.append("#"*100)
        for i in range(97):
            src.append(("#."*50)[:-1]+"#")
        src.append("#"+"."*98+"#")
        src.append("#"*100)
        #print "\n", "\n".join(src)
        matrix = Matrix("\n".join(src))
        #self.assertEquals(22, matrix.run())
        print matrix.run()

if __name__ == "__main__":
    unittest.main()

개선1

"어떤 고리들끼리 연결하는지를 안다면 그들을 연결하는 올바른 방법을 찾는 것은 쉽습니다." 라는 문제속의 힌트를 이용하여 나가는 구멍이 1개인 것만 대상으로 시작하도록 변경하도록 수정했더니 좀 빨라졌습니다.

하지만 파이썬의 최대 재귀호출수 제약때문에 11 x 300 정도까지밖에 테스트를 못 해 봤네요. 이정도 크기는 15초가량 걸립니다.

개선2

나가는 구멍이 1개인 것들을 모두 조사할 필요없이, 시작하는 1개만 찾아서 수행시키면 되네요.. 어차피 시작점과 끝점을 모두 찾기 때문에 한 개의 시작점만 검색해도 되겠죠.. 그리고 재귀호출 수행수를 줄이기 위해서 갈래길에서만 재귀를 수행하도록 수정했습니다. 덕분에 최대 재귀호출 수 오류는 발생하지 않게 되었습니다. 아.. 그래도 1000 x 1000 은 수행시간이 무척 오래걸리네요..

100 x 100 은 3초 정도 걸립니다. 제 능력으론 더 이상 줄이는건 무리일 듯 싶네요 ㅎ.

1000 x 1000 이 2초 내에 정말 가능할까요? ㅜㅜ

C코드

#include<stdio.h>

char map[1050][1050];//미궁 지도
int chk[1050][1050];//check array
int dx[5]={0,-1,0,1,};//방향 array
int dy[5]={1,0,-1,0,};
int Q[1000050][2];//Queue
int fr=0,rr=-1;
int ans;
int N,M;

void input(){
    scanf("%d %d",&M,&N);
    for(int i=0;i<N;i++){
        scanf("%s",map[i]);
    }
}

void solve(){
    int sx,sy;//Queue시작 지점(임의의 한점)
    for(int i=0;i<N;i++) for(int j=0;j<M;j++){
        if(map[i][j]=='.'){
            sx=i,sy=j;
            break;
        }
    }
    Q[++rr][0]=sx;
    Q[rr][1]=sy;
    chk[sx][sy]=1000000;
    while(fr<=rr){
        int x=Q[fr][0];
        int y=Q[fr++][1];
        for(int i=0;i<4;i++){
            if(map[x+dx[i]][y+dy[i]]=='.'&&chk[x+dx[i]][y+dy[i]]!=1000000){//'.'이고 chk배열에 chkeck가 안되어있으면
                Q[++rr][0]=x+dx[i];//Queue에 삽입
                Q[rr][1]=y+dy[i];
                chk[x+dx[i]][y+dy[i]]=1000000;//chk해줌
            }
        }
    }
    sx=Q[--fr][0];//끝까지 와서 다시 그 점부터 BFS시작
    sy=Q[fr][1];
    chk[sx][sy]=1;
    fr=0,rr=-1;
    Q[++rr][0]=sx;
    Q[rr][1]=sy;
    while(fr<=rr){
        int x=Q[fr][0];
        int y=Q[fr++][1];
        for(int i=0;i<4;i++){
            if(map[x+dx[i]][y+dy[i]]=='.'&&chk[x+dx[i]][y+dy[i]]>chk[x][y]){
                Q[++rr][0]=x+dx[i];
                Q[rr][1]=y+dy[i];
                chk[x+dx[i]][y+dy[i]]=chk[x][y]+1;//이 때 최장거리를 알 수 있다.
            }
        }
    }
    ans=chk[Q[--fr][0]][Q[fr][1]];
}

void output(){
    printf("Maximum rope length is %d.",ans-1);
}
int main(){
    input();
    solve();
    output();
    return 0;
}

C소스 입니다. 미궁 내부가 트리이므로 임의의 한 점을 잡아서 BFS를 두번 돌렸습니다. 1000by1000도 약1초안에 나올 것 같습니다. 또 pair와 Queue라이브러리를 사용하면 코드를 더 짧게 줄일 수도 있을 것 같네요..

.생각해보니 굳이 BFS를 두번 돌리지 않아도 될 것 같습니다. 시간복잡도는 거기서 거기지만... 사실 python을 배우려고 이 사이트에 들어왔습니다만, 이런 문제와 같은 본격적인(?)문제는 python으로 어떻게 짜야할지 감조차 오지 않네요 ㅠ 예를들어 BFS나 Queue와 같은 자료구조를 python으로는 어떻게 구현해야 할지 잘 모르겠습니다.

Imports System.Drawing

Module Module1
    Dim max_rope As Integer = 0

    Sub Main()
        Dim pt As New Point
        Dim lst As New List(Of Integer)

        For i As Integer = 1 To Integer.Parse(Console.ReadLine)
            Dim size() As String = Split(Console.ReadLine(), " ")

            Dim map(size(0) - 1, size(1) - 1) As Integer

            For y As Integer = 0 To size(1) - 1
                Dim input As String = Console.ReadLine()

                For x As Integer = 0 To input.Length - 1
                    If input(x) = "#" Then
                        map(x, y) = 1
                    Else
                        map(x, y) = 0
                        pt = New Point(x, y)
                    End If
                Next
            Next

            max_rope = 0

            BFS(map, pt, 1)

            lst.Add(If(max_rope > 1, max_rope, 0))
        Next

        For Each r As Integer In lst
            Console.WriteLine($"Maximum rope length is {r}.")
        Next
    End Sub

    Sub BFS(ByRef map(,) As Integer, pos As Point, weight As Integer)
        Dim dir() As Point =
        {
            New Point(-1, 0),
            New Point(0, -1),
            New Point(1, 0),
            New Point(0, 1)
        }

        max_rope = Math.Max(weight, max_rope)

        For Each d As Point In dir
            Dim dpt As Point = d + pos

            If (dpt.Y >= 0 AndAlso dpt.Y < map.GetLength(1)) AndAlso
                (dpt.X >= 0 AndAlso dpt.X < map.GetLength(0)) Then

                If map(dpt.X, dpt.Y) = 0 Then
                    map(dpt.X, dpt.Y) = 2
                    BFS(map, dpt, weight + 1)
                End If
            End If
        Next
    End Sub

End Module

코드가 미궁입니다 ㅠㅠ
성능을 우선적으로 생각하다보니 엄청 긴 코드가 되버렸네요.
기본적인 컨셉은, 일단 로프를 몽땅 연결했다고 생각하고 로프끝부붙을 점점 말아서 중심방향으로 들어간다고 생각했습니다.
교차점을 만나면 짧은 로프는 끊어서 버립니다.
다만, 짧은 로프가 포함된 부분이 정답이 될 가능성도 있으므로
그건 따로 리스트에 저장했습니다.
시간복잡도는 미궁의 면적에 비례합니다.

#-*- coding: utf-8 -*-
laby='''\
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######'''
laby=[list(x) for x in laby.split()]

def is_end(laby,r,c):
    return isinstance(laby[r][c],int) and\
     [laby[r+1][c],laby[r-1][c],laby[r][c+1],laby[r][c-1]].count('#')==3
def is_crossing(laby,r,c):
    return isinstance(laby[r][c],int) and\
     [laby[r+1][c],laby[r-1][c],laby[r][c+1],laby[r][c-1]].count('#')<=1
def is_normal_line(laby,r,c):
    return isinstance(laby[r][c],int) and\
     [laby[r+1][c],laby[r-1][c],laby[r][c+1],laby[r][c-1]].count('#')==2

def change_dot_to_1(laby):
    for i in range(len(laby)):
        for j in range(len(laby[0])):
            if laby[i][j]=='.': laby[i][j] = 1
def has_only_one_digit(laby,res):
    count=0
    for i in range(len(laby)):
        for j in range(len(laby[0])):
            if isinstance(laby[i][j],int):count+=1;theDigit=laby[i][j]
            if count > 1 : return False
    res.append(theDigit)
    display(laby,res)
    return True
def eat_end(laby,res):
    q=[]
    for i in range(len(laby)):
        for j in range(len(laby[0])):
            if is_end(laby,i,j):q.append((i,j))
    while q:
        (r,c) = q.pop()
        for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            if isinstance(laby[r+dr][c+dc],int) and not is_crossing(laby,r+dr,c+dc):
                laby[r+dr][c+dc] += laby[r][c]
                laby[r][c] = '#'
                display(laby,res)
                q.append((r+dr,c+dc))
def eat_crossing(laby,res):
    q=[]
    for i in range(len(laby)):
        for j in range(len(laby[0])):
            if is_crossing(laby,i,j):q.append((i,j))
    while q:
        (r,c) = q.pop()
        around=[]
        normal_line_count=0
        for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            if is_normal_line(laby, r+dr,c+dc):normal_line_count
        if normal_line_count >= 2 : continue
        for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            if is_end(laby, r+dr, c+dc):
                around.append(laby[r+dr][c+dc])
                laby[r+dr][c+dc]='#'
        around.sort(reverse=True)
        res.append(around[0]+around[1]+1)
        laby[r][c] += around[0]
        display(laby,res)

def display(laby,res):
    l = laby[:]
    for line in l:
        print ''.join(map(str,line))
    print 'res=',res
    print

def rope_len(laby):
    res=[]
    display(laby,[])
    change_dot_to_1(laby)
    display(laby,[])
    while not has_only_one_digit(laby,res):
        eat_end(laby,res)
        eat_crossing(laby,res)
    return  max(res)-1

r=rope_len(laby)
print "longest rope length:",r

'''
#######     점을 모두 1로 바꿉니다.
#.#.###
#.#.###
#.#.#.#
#.....#
#######
res= []

#######
#1#1###
#1#1###
#1#1#1#
#11111#
#######
res= []

#######    선의 끝에서부터 하나씩 #로 바꾸고
#1#1###    #로 바뀐 숫자를 그 앞의 숫자에 더합니다.
#1#1###
#1#1###
#11112#
#######
res= []

#######   다음 더할 숫자가 교차점이면 다른 점으로 넘어갑니다.
#1#1###
#1#1###
#1#1###
#1113##
#######
res= []

#######
#1#####
#1#2###
#1#1###
#1113##
#######
res= []

#######
#1#####
#1#####
#1#3###
#1113##
#######
res= []

#######
#######
#2#####
#1#3###
#1113##
#######
res= []

#######
#######
#######
#3#3###
#1113##
#######
res= []

#######
#######
#######
###3###
#4113##
#######
res= []

#######   교차점을 처리할 차례입니다.
#######   교차점 주변의 숫자중 가장 큰 두 숫자를 더하고 거기에
#######   교차점 자신의 값 1을 더해서 리스트에 넣습니다.
###3###   (3+5+1=9)
##513##
#######
res= []

#######   교차점 자신의 숫자는
#######   교차점 자신의 자신이 가지고 있던 1과
#######   주변 숫자중 가장 큰것(5,3,3 중 가장 큰 5)를 더해서
#######   6으로 바꿉니다.
###6###   이 과정이 필요한 이유는, 이 샘플에서는 필요없지만
#######   만약 아래방향으로 미궁이 이어진다면 6이라는 숫자가 필요하기 때문입니다.
res= [9]

#######   숫자가 하나만 남으면 결과리스트에 넣어줍니다.
#######
#######
#######
###6###
#######
res= [9, 6]

결과리스트중, 가장 큰값을 찾아서 1을 빼주고 출력합니다.
1을 빼주는 이유는 우리가 센것은 점의 갯수이기 때문입니다.
점의 갯수가 9개 이므로 그 9개의 점을 잇는 로프의 길이는 8입니다.

longest rope length: 8
'''

sample = list(x.split('\n') for x in ['''###
#.#
###''','''#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######'''])
class rope:
    def __init__(self, a = None):
        self.a = a
        self.b = []
    def append(self):
        self.b.append(rope(self))
        return self.b[-1]
    def length(self, depth = 0):
        if self.a == None:
            return depth
        else:
            return self.a.length(depth+1)
class m:
    def __init__(self, li):
        self.m = self.get_map(li)
    def get_map(self, li):
        return list(list(1 if x=='#' else 0 for x in y) for y in li)
    def move_list(self, y, x):
        return[(y+1,x),(y-1,x),(y,x+1),(y,x-1)]
    def chain(self, y, x, result = [], history = [], rp = rope()):
        li = self.move_list(y,x)
        nli = []
        for cy, cx in li:
            try:
                if (cy,cx) not in history and self.m[cy][cx] != 1:
                    nli.append((cy,cx))
            except IndexError:
                continue
        if len(nli) == 0:
            result.append(rp)
        else:
            for cy, cx in nli:
                self.chain(cy, cx, result, history+[(y,x)], rp.append())  
    def cal(self, result = []):
        for y in range(len(self.m)):
            for x in range(len(self.m[y])):
                if self.m[y][x] == 0:
                    self.chain(y, x, result)
                    return result

if __name__ == '__main__':
    for x in sample:
        print(max(y.length() for y in m(x).cal()))

로프는 a>b로 확장되며 b에는 여러 값이 올 수 있습니다. 그러므로 길이는 b 말단에서만 계산 가능합니다. 경로를 탐색한 후 b 말단을 결과에 저장합니다. 그 후 b로부터 a까지의 재귀호출 수를 구합니다. 이 값이 길이이며, b의 가능한 길이들 중에서 가장 긴 값을 내놓습니다.

파이썬 3.5.1

Delphi 2010 BSF 와 MEMORY 방식으로 모든 경우의 수 Check

// type
// TArrayInt2d = array of array of Integer;

function BFS(var Map: TArrayInt2d; var X, Y, L: array of Integer; pStart, pEnd: TPoint;
  sizeX, sizeY: Integer): Integer;
var
  i, pos, cnt, nSize, xPos, yPos: Integer; // 맵의 크기와 카운트 변수
  // 큐에 좌표 정보와 길이를 삽입하는 함수
  procedure enqueue(_x, _y, _l: Integer);
  begin
    X[cnt] := _x;
    Y[cnt] := _y;
    L[cnt] := _l;
    Inc(cnt);
  end;

begin
  pos := 0;
  cnt := 0;

  // 시작점의 좌표 정보와 길이를 큐에 삽입한다
  nSize := sizeY * sizeX;
  for i := 0 to nSize - 1 do
  begin
    X[i] := 0;
    Y[i] := 0;
    L[i] := 0;
  end;

  enqueue(pStart.X, pStart.Y, 1);
  X[pos] := pStart.X;
  Y[pos] := pStart.Y;
  // 더 이상 방문할 지점이 없거나, 도착 지점에 도착하면 루프를 탈출한다
  result := -1; // 결과값 저장
  while (pos < nSize) do
  begin
    yPos := Y[pos];
    xPos := X[pos];
    if (xPos = pEnd.X) and (yPos = pEnd.Y) then // 결과위치
      exit(pos);

    if (xPos >= sizeX - 1) and (yPos >= sizeY - 1) then
      exit;

    // 두 번 방문하게 하면 안되므로, 이미 지나갔다는 표시를 해둔다
    Map[yPos, xPos] := 0;
    // 위로 갈 수 있다면, 위 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (yPos > 0) and (Map[yPos - 1, xPos] = 1) then
      enqueue(xPos, yPos - 1, L[pos] + 1);
    // 아래로 갈 수 있다면, 아래 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (yPos < sizeY - 1) and (Map[yPos + 1, xPos] = 1) then
      enqueue(xPos, yPos + 1, L[pos] + 1);
    // 왼쪽으로 갈 수 있다면, 왼쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (xPos > 0) and (Map[yPos, xPos - 1] = 1) then
      enqueue(xPos - 1, yPos, L[pos] + 1);
    // 오른쪽로 갈 수 있다면, 오른쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (xPos < sizeX - 1) and (Map[yPos, xPos + 1] = 1) then
      enqueue(xPos + 1, yPos, L[pos] + 1);

    // 큐의 다음 순서의 지점을 방문한다
    Inc(pos);
  end;
end;

procedure TForm4.btn미로최대길이Click(Sender: TObject);
var
  sData: string;
  C: Char;
  i, j, k, k1, k2, n1, n2, n3, nSizeX, nSizeY, nSize, nMax, pos, Pos2: Integer;
  Map, Map2, RST: TArrayInt2d;
  pStart, pEnd, pStart2, pEnd2: TPoint;
  X, X2, Y, Y2, L, L2, V: array of Integer; // 좌표와 길이를 담을 배열
  StartValue: DWORD;
  function Result_Value(pos: Integer): string;
  var
    i: Integer;
    s: string;
  begin
    s := '';
    result := '';
    for i := 0 to pos do
      s := s + format('%3d,', [Y2[i]]);
    result := result + #13#10 + ' Y Value: ' + s;
    for i := 0 to pos do
      s := s + format('%3d,', [X2[i]]);
    result := result + #13#10 + ' X Value: ' + s;
    s := '';
    for i := 0 to pos do
      s := s + format('%3d,', [L2[i]]);
    result := result + #13#10 + ' L Value: ' + s;
    if pos <> -1 then
      pos := L2[pos];
    s := format('Max: %d  Start: %d,%d  End: %d,%d', [pos, pStart2.Y, pStart2.X, pEnd2.Y, pEnd2.X]);
    result := s + #13#10 + result;
  end;

  function fx(i, j: Integer): Integer;
  begin
    result := i * nSizeX + j;
  end;

  procedure fb(val: Integer; var i, j: Integer);
  begin
    i := val div nSizeX;
    j := val mod nSizeX;
  end;

  procedure SetRST(val: Integer; i, j: Integer);
  begin
    RST[i, j] := val;
    RST[j, i] := val;
  end;

begin

  nSizeX := 7;
  nSizeY := 6;
  sData := //
    '#######' + //
    '#.#.###' + //
    '#.#.###' + //
    '#.#.#.#' + //
    '#.....#' + //
    '#######';

  { nSizeX := 40;
    nSizeY := 40;
    SetLength(sData, nSizeX * nSizeY);
    Randomize;
    for i := 1 to nSize do
    if Random(2) = 1 then
    sData[i] := '1'
    else
    sData[i] := '0';
    }
  // 변수 Array 메모리 할당
  nSize := nSizeY * nSizeX;
  SetLength(X, nSize);
  SetLength(Y, nSize);
  SetLength(L, nSize);
  SetLength(X2, nSize);
  SetLength(Y2, nSize);
  SetLength(L2, nSize);
  SetLength(V, nSize); // Visite
  SetLength(Map, nSizeY, nSizeX);
  SetLength(Map2, nSizeY, nSizeX);
  SetLength(RST, nSize, nSize);
  // 변수 Array 초기화
  for i := 0 to nSize - 1 do
    V[i] := 1;
  for i := 0 to nSize - 1 do
    for j := 0 to nSize - 1 do
      RST[i, j] := -1;

  // Map Data 분석
  pStart := Point(0, 0);
  pEnd := Point(nSizeY - 1, nSizeX - 1);
  for i := 0 to nSizeY - 1 do
    for j := 0 to nSizeX - 1 do
    begin
      C := sData[nSizeX * i + j + 1];
      if (C = '#') or (C = '0') then
      begin
        Map[i, j] := 0;
        Map2[i, j] := 0;
        k2 := fx(i, j);
        V[k2] := 0;
        for k := 0 to nSize - 1 do
          SetRST(0, k2, k); // 경로 찾기 과정을 생략함.
      end
      else
      begin
        // k2 := fx(i, j);
        // V[k2] := 1;
        Map[i, j] := 1;
        Map2[i, j] := 1;
      end;
    end;

  nMax := 0; // 최대치 값
  StartValue := GetTickCount;

  for i := 0 to nSize - 1 do // 모든 경우의 수를 구한다.
    if V[i] = 1 then
    begin
      n1 := i; // 시작위치   ( Y*nSizeX + Y)
      for n3 := 0 to nSize - 1 do
      begin
        n2 := i; // 마지막 위치
        for j := nSize - 1 downto 0 do
          if V[j] = 1 then
            if RST[n1, j] = -1 then
            begin
              n2 := j; // ( Y*nSizeX + Y)
              break;
            end;
        if n1 = n2 then // 더이상 새로운 곳이 아니면 종료
          break;
        // Map 초기화
        for k1 := 0 to nSizeY - 1 do
          for k2 := 0 to nSizeX - 1 do
            Map[k1, k2] := Map2[k1, k2];

        // 시작 종료 값 설정
        fb(n1, pStart.Y, pStart.X);
        fb(n2, pEnd.Y, pEnd.X);
        // BFS 탐색
        pos := BFS(Map, X, Y, L, pStart, pEnd, nSizeX, nSizeY); // BFS 시작!
        if pos = -1 then // 실폐하면
        begin
          SetRST(0, n1, n2); // 해당경로 찾기를 Clear함.
        end
        else
        begin
          if nMax < L[pos] then
          begin
            nMax := L[pos]; // 결과의 최대값 반영
            Pos2 := pos;

            // 최대값의 계산 결과값을 저장함.
            pStart2 := pStart;
            pEnd2 := pEnd;
            for k := 0 to nSize - 1 do
            begin
              X2[k] := X[k];
              Y2[k] := Y[k];
              L2[k] := L[k];
            end;
          end;
          SetRST(L2[pos], n1, n2); // 결과값 저장 //경로 찾기 Clear;
          // 찾기 중간의 모든 경로 찾기 Clear; 중복 제거
          for k1 := 0 to pos do
            for k2 := k1 to pos do
            begin
              n1 := fx(Y[k1], X[k1]);
              n2 := fx(Y[k2], X[k2]);
              SetRST(1, n1, n2); // 경로 찾기 설정
            end;
        end;
      end;

    end;
  // 결과 값 Report
  StartValue := GetTickCount - StartValue;
  Memo1.Lines.Text := format('%.3n Sec', [StartValue / 1000]) + #13#10 + '미로최대길이 =  ' + IntToStr(nMax)
    + #13#10 + Result_Value(Pos2); // BFS 시작!
end;

Ruby

BFS. 인접경로 발견시 길이 1증가.

max_rope_length = ->rows=gets.split[1].to_i do
  labyrinth = Matrix[*(1..rows).map { gets.chop.chars }]
  q, max_len = [labyrinth.index(".") << -1], 0

  road = ->pos { r,c,_ = pos; r>=0 && c>=0 && labyrinth[r,c] == "." }
  adjs = ->r,c,len { [[1,0],[-1,0],[0,-1],[0,1]].map {|y,x| [r+y,c+x,len]}.select(&road) }
  nexts = ->r,c,len { labyrinth.send(:[]=, r, c, "#")
                      max_len = [max_len, len+1].max; adjs[r,c,len+1] }
  q += nexts[*q.shift] until !q[0]
  "Maximum rope length is #{max_len}."
end
max_ropes = -> { puts (1..gets.to_i).map { max_rope_length[] } }

Test

test_inputs = "2\n" +
              "3 3\n" +
              "###\n" +
              "#.#\n" +
              "###\n" +
              "7 6\n" +
              "#######\n" +
              "#.#.###\n" +
              "#.#.###\n" +
              "#.#.#.#\n" +
              "#.....#\n" +
              "#######\n"
expected_stdout = "Maximum rope length is 0.\n" +
                  "Maximum rope length is 8.\n"
$stdin = StringIO.new(test_inputs)
expect { max_ropes.call }.to output( expected_stdout ).to_stdout

C#으로 작성했습니다. Queue를 개조해서 사용했습니다.

using System.Collections.Generic;

        public class Queue
        {
            public List<int> X { get; set; }
            public List<int> Y { get; set; }
            public List<int> Z { get; set; }
            public int Count { get; set; }

            public Queue()
            {
                X = new List<int>();
                Y = new List<int>();
                Z = new List<int>();
                Count = 0;
            }

            public void Enqueue(int x, int y, int z)
            {
                X.Add(x);
                Y.Add(y);
                Z.Add(z);
                Count++;
            }

        }

        public int MaxDistance(string[,] board, int x, int y)
        {
            var count = 0;
            var max = 0;
            var queue = new Queue();
            var shiftX = board.GetLength(0);
            var shiftY = board.GetLength(1);
            if (board[x, y] == "#") return count;
            queue.Enqueue(x, y, 0);
            while (count < queue.Count && (queue.X[count] < shiftX || queue.Y[count] < shiftY))
            {
                var tempX = queue.X[count];
                var tempY = queue.Y[count];
                var tempZ = queue.Z[count];
                board[tempX, tempY] = "#";
                if (tempX > 0 && board[tempX -1, tempY] == ".")
                    queue.Enqueue(tempX - 1, tempY, tempZ + 1);
                if (tempX < shiftX - 1 && board[tempX + 1, tempY] == ".")
                    queue.Enqueue(tempX + 1, tempY, tempZ + 1);
                if (tempY > 0 && board[tempX, tempY - 1] == ".")
                    queue.Enqueue(tempX, tempY - 1, tempZ + 1);
                if (tempY < shiftY - 1 && board[tempX, tempY + 1] == ".")
                    queue.Enqueue(tempX, tempY + 1, tempZ + 1);
                count++;
                if (max < queue.Z[queue.Z.Count - 1]) max = queue.Z[queue.Z.Count - 1];
            }
            return max;
        }

#include <stdio.h>
#include <stdlib.h>
char** labyrinth;
int** flag;
int findPath(int r, int c, int weight);
int* max;
int mindex = 0;
int main() {
    int T , R, C;
    scanf("%d", &T);
    max = (int*) malloc (sizeof(int) * T);
    for(int index = 0; index < T; index++) {
        scanf("%d %d", &R, &C);
        labyrinth = (char**) malloc (sizeof(char*) * R);
        for(int i=0;i<R ;i++)
            labyrinth[i] =  (char*) malloc (sizeof(char) * C);
        flag = (int**) malloc (sizeof(int*) * R);
        for(int i=0;i<R ;i++)
            flag[i] =  (int*) malloc (sizeof(int) * C);

        for(int i=0;i<R ;i++) {
            scanf("%s", labyrinth[i]);
        }
        for(int i=0;i<R ;i++) {
            for(int j=0;j<C ;j++) {
                if(labyrinth[i][j]=='#') flag[i][j] = 0;
                else flag[i][j] = 1;
            }
        }

        for(int i=0;i<R ;i++) {
            for(int j=0;j<C ;j++) {
                if(flag[i][j] == 1)
                    findPath(i,j,0);
            }
        }
        mindex++;
    }

    for(int i = 0;i<T;i++)
        printf("maximum rope length is %d.\n", max[i]);

    return 0;
}

int findPath(int r, int c, int weight) {
    int count=0;
    if(flag[r][c] == 0)
        return weight;
    flag[r][c] = 0;

    if(flag[r][c-1] == 0 && flag[r][c+1] == 0 && flag[r-1][c] == 0 && flag[r+1][c] == 0) {
        if(max[mindex] < weight)
            max[mindex] = weight;
    }

    if(labyrinth[r][c-1] == '.' && flag[r][c-1] != 0) {
        weight++;
        findPath(r, c-1, weight);
        count++;
    }
    if(labyrinth[r][c+1] == '.' && flag[r][c+1] != 0) {
        weight = weight - count;
        weight++;
        findPath(r, c+1, weight);
        count++;
    }
    if(labyrinth[r-1][c] == '.' && flag[r-1][c] != 0) {
        weight = weight - count;
        weight++;
        findPath(r-1, c, weight);
        count++;
    }
    if(labyrinth[r+1][c] == '.' && flag[r+1][c] != 0) {
        weight = weight - count;
        weight++;
        findPath(r+1, c, weight);
        count++;
    }

    return weight;
}

Kim Jaeju 님의 아이디어를 참고하여 Haskell로 구현하였습니다. 임의의 위치에서 가장 먼곳을 찾고, 거기서 다시 가장 먼곳을 찾는 방식입니다.

{-# LANGUAGE QuasiQuotes,TupleSections #-}
import Text.RawString.QQ
import Data.Array

maze1 = [r|###
#.#
###|]

maze2 = [r|#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######|]

type Dist = Int
type Pos = (Int,Int)
type Maze = Array Pos Char

emptyCell maze = fst $ head $ filter (\(pos, c) -> c == '.') $ assocs maze

neighbors :: Maze -> Pos -> [Pos]
neighbors m (x,y) = [ p |
  p <- [(x-1,y), (x+1,y), (x,y-1), (x,y+1)],
  inRange (bounds m) p,
  m ! p == '.']

farthest :: Pos -> Maze -> (Dist, Pos)
farthest pos m = last $ bfs pos (neighbors m)

bfs :: Eq a => a -> (a -> [a]) -> [(Int, a)]
bfs start next = visit start [] 0
  where visit cur visited d = (d,cur) : concat [visit p (cur:visited) (d+1)| 
                p <- next cur,
                not (p `elem` visited)] 

labyrinth :: Maze -> Int
labyrinth maze = d
  where a = emptyCell maze
        (_,b) = farthest a maze
        (d,_) = farthest b maze

mazeFrom str bnd = array ((1,1),bnd)
                [ ((r,c),cell) | (r,row) <- zipWith (,) [1..] (lines str),
                                 (c,cell)<- zipWith (,) [1..] row]

main = do
  print $ labyrinth $ mazeFrom maze1 (3,3)
  print $ labyrinth $ mazeFrom maze2 (6,7)

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

class Point{
    int x;
    int y;

    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Maze {

    public static void execute(int c, int r, String[][] maze){

        Queue<Point> queue = new LinkedList<>();

        queue.offer(new Point(1, c/2));
        maze[1][c/2] = 0 +"";

        boolean wayFlag = false; // 막다른곳이면 false, 다른곳으로 이동 가능이면 true

        List<Integer> falseWayList = new ArrayList<>();

        while(!queue.isEmpty()){ //BFS 큐가 비어있지 않은 경우

            Point point = queue.poll();

            wayFlag = false;
            // 갈수 있는 경로 큐에 추가
            if(point.x > 0 && maze[point.x-1][point.y].equals(".")){ // 위
                maze[point.x-1][point.y] = Integer.parseInt(maze[point.x][point.y])+1 + "";
                queue.offer(new Point(point.x-1, point.y));
                wayFlag= true;
            }
            if(point.x < r-1 && maze[point.x+1][point.y].equals(".")){ // 아래
                maze[point.x+1][point.y] = Integer.parseInt(maze[point.x][point.y])+1 + "";
                queue.offer(new Point(point.x+1, point.y));
                wayFlag= true;
            }
            if(point.y > 0 && maze[point.x][point.y-1].equals(".")){ // 왼쪽
                maze[point.x][point.y-1] = Integer.parseInt(maze[point.x][point.y])+1 + "";
                queue.offer(new Point(point.x, point.y-1));
                wayFlag= true;
            }
            if(point.y < c-1 && maze[point.x][point.y+1].equals(".")){ // 오른쪽
                maze[point.x][point.y+1] = Integer.parseInt(maze[point.x][point.y])+1 + "";
                queue.offer(new Point(point.x, point.y+1));
                wayFlag= true;
            }

            if(!wayFlag){ // 구석인 경우
                if(!maze[point.x][point.y].equals("e")){
                    falseWayList.add(Integer.parseInt(maze[point.x][point.y]));
                }
            }
        }

        Collections.sort(falseWayList);

        System.out.println("Maximum rope length is " + (falseWayList.size() > 0 ? falseWayList.get(falseWayList.size()-1)  : 0) + ".");


    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();  //테스트케이스 수

        for(int i=0; i<t; i++){

            int c = sc.nextInt(); // 열 수 3 <= C
            int r = sc.nextInt();  // 행 수 R <= 1000
            sc.nextLine(); // 줄바꿈 삭제
            String[][] maze = new String[r][c]; // 미로 배열

            for(int j=0 ; j < r; j++){
                String[] str = sc.nextLine().split("");
                for(int k=0; k < str.length; k++){
                    maze[j][k] = new String(str[k]);
                }
            }

            execute(c, r, maze);

        }

    }

}

from collections import defaultdict

class labyrinth:
    def __init__(self,mat):
        self.mat = mat
        self.tree = defaultdict(dict)
        self.row,self.clm = len(self.mat),len(self.mat[0])

    def __search_near(self,x,y):
        result = []
        drt = ((0,-1),(0,1),(1,0),(-1,0))
        for dx,dy in drt:
            if not(0<= x+dx <self.row and 0<= y+dy <self.clm): continue
            if self.mat[x+dx][y+dy] == '.': result.append((x+dx,y+dy))
        return result

    def __search_startpos(self):
        for i in range(self.row):
            for j in range(self.clm):
                if len(self.__search_near(i,j)) in (0,1) and self.mat[i][j] == '.': return (i,j)

    def __make_tree(self):
        curpos = self.__search_startpos()
        stack = [[curpos,[],0]]
        cnt,mx = 0,[0,curpos,curpos]
        visited = [curpos]
        while stack:
            nextpos = [i for i in self.__search_near(*curpos) if i not in visited]
            if len(nextpos) != 1:
                self.tree[curpos][stack[-1][0]] = cnt - stack[-1][2]
                self.tree[stack[-1][0]][curpos] = cnt - stack[-1][2]

            if len(nextpos) > 1:
                stack.append([curpos,nextpos,cnt])

            elif len(nextpos) == 0:
                if mx[0] < cnt: mx[0],mx[2] = cnt,curpos
                while 1:
                    if stack == []: break
                    if stack[-1][1]==[]:
                        stack.pop()
                        continue
                    else:
                        curpos = stack[-1][1].pop()
                        visited.append(curpos)
                        cnt = stack[-1][2] + 1
                        break
                continue
            curpos = nextpos.pop()
            visited.append(curpos)
            cnt += 1
        return mx

    def __exp_tree(self,startpos):
        queue = list(self.tree[startpos].items())
        mx = [0,startpos,startpos]
        visited = []
        while queue:
            curpos,cnt = queue.pop()
            visited.append(curpos)
            for i,j in self.tree[curpos].items():
                if i not in visited:
                    queue.insert(0,(i,j+cnt))
                    if j+cnt > mx[0]: mx[0],mx[2] = j+cnt,i
        return mx

    def main(self):
        ans,spos,epos = self.__make_tree()
        while 1:
            tmp = self.__exp_tree(epos)
            if ans == tmp[0]: return 'from {1} to {2}\nMaximum rope length is {0}.'.format(*tmp)
            else: ans,epos = tmp[0],tmp[2]

처음 미궁을 임의의 시작점에서 DFS로 탐색하여 트리를 구성하고, 가장 긴 루트를 검색
검색된 루트의 끝지점을 새로운 시작점으로 하여 위에서 만든 트리를 BFS로 탐색하여 가장 긴 루트 검색
가장 긴 루트의 길이와 그전 길이가 같을때까지 반복

테스트

case = ['''\
###
#.#
###''','''\
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######''','''\
####################
##########.#####.###
#.............##.###
#######.##.##.##.###
######..##.##.##.#.#
####...###.##....#.#
#....#.###.#######.#
#.####.#.#.........#
#.####.#.#.#######.#
#.####.#.#.#######.#
#.######.......###.#
#......#.#.###.###.#
#.####.#.#.###.###.#
#.####.#.#.###...#.#
#.####.#.#.###.#.#.#
#.####.#.#.###.#.#.#
#.####.###.###.#.#.#
#.####.###.#####.#.#
#.####.###.#######.#
####################''']

for i in (i.split('\n') for i in case):
    test = labyrinth(i)
    print(test.main(),'\n')

결과

from (1, 1) to (1, 1)
Maximum rope length is 0.

from (1, 3) to (1, 1)
Maximum rope length is 8.

from (18, 18) to (18, 6)
Maximum rope length is 54.

checkedP = set()
maxN = 0

def move(r,c, lst, P,C,R):
    global checkedP, maxN
    ismove = False
    for m in [(-1,0),(0,1),(1,0),(0,-1)]:
        mr, mc = r+m[0], c+m[1]
        if 0<=mr<R and 0<=mc<C and P[mr][mc]=='.' and (mr*C + mc) not in lst:
            ismove = True
            checkedP.add(mr*C + mc)
            newlst = lst.copy()
            newlst.append(mr*C + mc)
            move(mr,mc,newlst,P,C,R)
    if ismove==False:
        maxN = max(maxN,len(lst)-1)

def ropeLength(P,C,R):
    global checkedP, maxN
    maxN = 0
    m=0
    while m<C*R:
        if P[m//C][m%C]=='.' and m not in checkedP:
            checkedP.add(m)
            move(m//C, m%C, [m], P, C, R)
        m += 1
    return maxN

# C, R = 3, 3
# inp = """###
# #.#
# ###"""

C, R = 7, 6
inp = """#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######"""

pyramid = [[x for x in r] for r in inp.split('\n')]
print("Maximum rope length is ", ropeLength(pyramid, C,R))