Advertisement
Guest User

Untitled

a guest
Feb 25th, 2021
264
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.49 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 10;
  8.  
  9. //row 0 & n+1, column 0 & n+1 are kept empty to provide safe boundary for the data
  10. char matrix[MAXN+2][MAXN+2];
  11. int n = 0;
  12.  
  13. int maxMatchedLength = 0;
  14.  
  15. void findMatchingClose(int count, int r, int c, int maxOpenCount) {
  16. if (count == 0) {
  17. if (maxMatchedLength < maxOpenCount)
  18. maxMatchedLength = maxOpenCount;
  19. return;
  20. }
  21.  
  22. //more digging; count > 0
  23.  
  24. if (matrix[r][c] != ')')
  25. return;
  26.  
  27. //digging for matching )
  28. findMatchingClose(count-5, r-1, c-1, maxOpenCount);
  29. //...
  30.  
  31. }
  32.  
  33. //start from (r,c), return the longest sequence of "(" found
  34. void findMaxOpen(int count, int r, int c) {
  35.  
  36. if (matrix[r][c] != '(') {
  37. findMatchingClose(count, r, c, count);
  38. return;
  39. }
  40.  
  41. //confirmed as '('
  42. matrix[r][c] = ' ';
  43.  
  44. findMaxOpen(count+1, r+1, c);
  45. findMaxOpen(count+1, r-1, c);
  46. findMaxOpen(count+1, r, c+1);
  47. findMaxOpen(count+1, r, c-1);
  48.  
  49. matrix[r][c] = '(';
  50. }
  51.  
  52. int main()
  53. {
  54.  
  55. cin >> n;
  56. //row 0 & n+1, column 0 & n+1 are kept empty to provide safe boundary for the data
  57. for(int i=1; i<=n; i++)
  58. for(int j=1; j<=n; j++)
  59. cin >> matrix[i][j];
  60.  
  61. findMaxOpen(0, 1,1);
  62. cout << maxMatchedLength*2;
  63.  
  64. //testing i/o
  65. // for(int i=1; i<=n; i++)
  66. // cout << &matrix[i][1] << endl;
  67. }
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement