/* http://usaco.org/index.php?page=viewproblem2&cpid=189 (create a free account) USACO 2012 November Bronze Ques. 3: Horseshoes This code is not for Sololearn, I recommend onlinegdb.com or visual studio code Make a file named highcard.in and put in: 4 (()) ()(( (()( )))) Output: 8 I recommend not copying this code into USACO though it works cause you need to do it yourself. */ #include #include #include #include // #include using namespace std; vector horseshoes; int result = 0; int n; void rec(int x, int y, int left_val, int right_val, vector > visited){ int xs[4] = {-1, 0, 1, 0}; int ys[4] = {0, 1, 0, -1}; visited[y][x] = 1; if(left_val == right_val && left_val + right_val > result){ result = left_val + right_val; return; } for(int i = 0; i < 4; i++){ int nx = x + xs[i]; int ny = y + ys[i]; if(!(nx < 0 || nx >= n) && !(ny < 0 || ny >= n) && !visited[ny][nx]){ if(horseshoes[ny][nx] == ')'){ // if(left_val > result /2){ // rec(nx, ny, left_val, right_val + 1, visited); // } rec(nx, ny, left_val, right_val + 1, visited); } else if(horseshoes[ny][nx] == '(' && right_val == 0){ rec(nx, ny, left_val + 1, right_val, visited); } } } } int main(){ ifstream fin("hshoe.in"); ofstream fout("hshoe.out"); fin >> n; vector > visited(n, vector(n)); for(int i = 0; i < n; i++){ string horseshoe; fin >> horseshoe; horseshoes.push_back(horseshoe); } if(horseshoes[0][0] == ')'){ fout << 0 << endl; } else{ rec(0, 0, 1, 0, visited); fout << result << endl; } fout.close(); fin.close(); return 0; }

USACO #32: Horseshoes C++