Horseshoes

Bessie the cow finds every balanced-parenthesis string pleasing, but she especially loves strings she calls perfectly balanced: a run of ( characters followed by an equally long run of ) characters. For example:

(((())))

One day, while walking through the barn, Bessie finds an $N \times N$ grid of horseshoes, each oriented so that it looks like either ( or ). Starting from the upper-left corner, she wants to walk around picking up horseshoes so that the string she collects is perfectly balanced. Compute the length of the longest perfectly balanced string she can obtain.

On each step Bessie may move up, down, left, or right. She may only move onto a cell that still contains a horseshoe; when she steps onto it she picks the horseshoe up, so the cell becomes empty and she can never return to it. She always begins by picking up the horseshoe in the upper-left corner. Bessie only keeps a sequence of horseshoes that forms a perfectly balanced string, so she may not be able to pick up every horseshoe in the grid.

• Line 1: an integer $N$ ($2 \le N \le 5$).
• Lines 2 through $N+1$: each line is a string of $N$ parentheses. Together these $N$ lines describe the $N \times N$ grid.

• Line 1: the length of the longest perfectly balanced string of horseshoes Bessie can collect. If she cannot collect any balanced string (for example, if the upper-left cell is )), output 0.

The diagram below shows one grid together with a collection order that yields a perfectly balanced string of length 8. Each digit marks the step at which that cell's horseshoe is picked up; cells that still show a parenthesis are never visited.

1())
2)((
345(
876)

Reading the picked-up horseshoes in step order gives (((()))), which is perfectly balanced and has length 8.