Solution Notes (Kalki Seksaria):

This problem can be solved by recursion, and we can try all possible paths. The part of the path consisting of '(' is constructed first, and this corresponds to second = false. Once a ')' is found, second is marked as true and only ')' can be added to the path. When numopen = numclose, this path is over. An additional optimization can optionally be made. If the '(' part of the path is over, then the length of the path, if it exists, is 2*numopen. If this cannot be better then the best answer found, then there is no reason to continue exploring this path.


#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define pii pair<int,int>
int N;
bool unvis[7][7];
int graph[7][7]; //-1 is border, 0 is open, 1 is close
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ans = 0;
void calc(int r, int c, int numopen, int numclose, bool second)
{
    if(numopen == numclose)
    {
        ans = max(ans, numopen + numclose);
        return;
    }
    
    //there is no need to check solutions that we know cannot be better than the best answer that we have found so far
    //this optimization is not required to solve the given test cases within 1 second
    if(second && (2*numopen <= ans))
        return;
    
    unvis[r][c] = false;
    
    for (int i = 0; i < 4; i++)
    {
        int r2 = r + dx[i];
        int c2 = c + dy[i];
        
        if(unvis[r2][c2])
        {
            if(graph[r2][c2] == 1)
                calc(r2, c2, numopen, numclose + 1, true);
            else if(!second)
                calc(r2, c2, numopen + 1, numclose, false);
        }
    }
    
    unvis[r][c] = true;
}
int main()
{
    ifstream in ("hshoe.in");
    ofstream out ("hshoe.out");
    
    in >> N;
    for (int i = 0; i <= N+1; i++) //adding a border around the grid makes it easier to check if a location is within the grid
    {
        unvis[0][i] = unvis[N+1][i] = unvis[i][0] = unvis[i][N+1] = false;
        graph[0][i] = graph[N+1][i] = graph[i][0] = graph[i][N+1] = -1;
    }
                                            
    for (int i = 1; i <= N; i++)
    {
        string s;
        in >> s;
        for (int j = 1; j <= N; j++)
        {
            unvis[i][j] = true;
            if(s[j-1] == '(')
                graph[i][j] = 0;
            else
                graph[i][j] = 1;
        }
    }
    
    if(graph[1][1] == 0)
        calc(1,1,1,0,false);
    out << ans << "\n";
    out.close();
    return 0;
}