Settlers of Catan - Longest Road!

Question

This is an endgame board of Settlers of Catan:

Background:

The roads (the long stick pieces) and the settlements (and cities) are rendered by the little huts. We encode the placement of these pieces by using the following scheme: From the top, we have a row horizontal vertices and edges where a road can be placed. Then we have a column of only roads, and so forth. Using R for Red, O for Orange, and B for Blue, and _ for nothing, the pictured board would be encoded as:

________RR_R_
__R_
__RR_R_RRR_____R_
B___R
_B_________B__OO_OOR_
B__B_R
BB_BBB_____B____RR_R_
OBB_O
OO__BB_BB__OOO_OO
O_O_
_O_OOO_O_____

A board like this will be your input string. Any letter [A-Z] may indicate a player color, but there will at most four colors (including empty). Boards are otherwise guaranteed to be valid according to the rules of Settlers, which means:

• Each color will have at most two contiguous road networks, which may or may not be broken apart by other players settlements / cities (vertex buildings). See the orange settlement breaking apart the red road on the right side of the sample image.
  • Each road network is guaranteed to have at least one settlement.
• All settlements and cities are guaranteed to be at least two edges from the nearest other settlement / city (yours or otherwise)
• One player may only have 15 roads on the game board.
• For Catan enthusiasts: there is no distinction between settlements and cities for the purpose of this problem, so I don't distinguish in the input string.

All this is for the specification of the "input" string.

Longest Road:

In Settlers, players get two victory points for having the "longest road". This is defined to be: The longest contiguous single path (measured in roads) from start point to end point, that is not broken up by an opponents settlement or city. Cycles are okay, as long as you can trace the path from one particular start point to one particular end point. So, a loop of 6 roads plus one road branching off is length 7, but one with two branching off the 6 road loop on opposite sides is still only worth 7.

In the example map, the Red road on the right side is only worth 4, because he is cut off by an Orange settlement on the right side of the board (that's why settlements are included at all). Blue has a road of length 13, and Orange has a road of length 12. Red's top road is only worth 7, because it doesn't connect to the two single roads next to it.

Output:

All players that have a road of the longest length (it could be more than one if there are ties), followed by a whitespace and/or underscore delimited count in base 10 of how long that road is.

So the output for the example board would be:

B 13

The Problem statement:

You may write a program or function, receives the input board via STDIN or as a string argument to your function, which returns the output described above as a string or prints it to STDOUT (or closest alternative). You may optionally include a single trailing newline in the output.

This is code-golf, shortest program wins. Standard loopholes are banned, of course.

Answer 1

Python 2, 445 400 bytes

I'm a fan of Settlers, so this challenge was fun.

T="^"
Z=26
A=T*52
for i in range(11):A+=(T*(i%2)*3).join(x for x in raw_input()).center(Z,T)
A+=T*52
def f(c,p=0,l=0,B=A):
 b=l;C=B[0:p]+T+B[p+1:];n=(Z,1)[p%2]
 for i in(p<1)*range(390):
    if(i/Z%2<1&i%2>0)|(i/Z%2>0&i%2<1):b=max(b,f(c,i))
 for i in(p-n,p+n)*(B[p]==c):
    for j in(i-Z,i-1,i+1,i+Z)*(B[i]in c+"_"):b=max(b,f(c,j,l+1,C))
 return b
i=l=0
for x in A:
 if x<T:i=f(x)
 if i>l:c=x;l=i
print c,l

Score reflects replacing each occurrence of 4 spaces with a tab.

Explanation

The lines before the function definition read the input, and build a normalized board into a single string variable. The process inserts "^" characters into the short lines representing the vertical road segments. It also pads the board with "^" characters.

^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^________RR_R_^^^^^^^
^^^^^^_^^^_^^^R^^^_^^^^^^^
^^^^__RR_R_RRR_____R_^^^^^
^^^^B^^^_^^^_^^^_^^^R^^^^^
^^_B_________B__OO_OOR_^^^
^^B^^^_^^^_^^^B^^^_^^^R^^^
^^BB_BBB_____B____RR_R_^^^
^^^^O^^^B^^^B^^^_^^^O^^^^^
^^^^OO__BB_BB__OOO_OO^^^^^
^^^^^^O^^^_^^^O^^^_^^^^^^^
^^^^^^_O_OOO_O_____^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^

When called with the default parameters, the function returns the length of a road of a given color. The first loop is active only when the position (p) parameter was supplied. It recursively finds the length of the road at each valid road position, and keeps track of the longest one. When there is a road at the position parameter, the function recursively adds the length of adjacent roads of the same color. The road is replaced with a "~" in the working copy of the board to ensure it doesn't recount segments that have already been counted.

The code following the function definition calls the function for each color in the board, and prints the highest scoring color and length.

Demo it here