Source code for submission s874

fq.cpp

  1. #include <algorithm>
  2. #include <cmath>
  3. #include<cstdio>
  4. #include <cstring>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <list>
  8. #include <map>
  9. #include <queue>
  10. #include <set>
  11. #include <stack>
  12. #include <string>
  13. #include <vector>
  14.  
  15. using namespace std;
  16.  
  17. #define REP(i,n) for ( int i = 0; i < (n); i++)
  18. #define FOR(i,a,b) for ( int i = (a); i <= (b); i++ )
  19. #define FORD(i,a,b) for ( int i = (a); i>= (b); i-- )
  20. #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
  21.  
  22. struct node {
  23. int i,j;
  24. int previ, prevj;
  25. };
  26.  
  27. string s;
  28. queue<node> q;
  29. int m = 100000,len;
  30. int table [1010][1010];
  31. bool states [1010][1010];
  32.  
  33. void bfs () {
  34. node n, pos;
  35. n.i = n.j = 0;
  36. n.previ = n.prevj = 0;
  37. q.push(n);
  38. while (!q.empty()) {
  39. pos = q.front();
  40. q.pop();
  41. //cout << s[pos.i+pos.j-1] << endl;
  42. if (pos.previ < pos.i && s[pos.i+pos.j-1] == ')') continue;
  43. if (pos.prevj < pos.j && s[pos.i+pos.j-1] == '(') continue;
  44. if (2*pos.i > len) continue;
  45. if (pos.j > pos.i) continue;
  46. if (pos.i != pos.previ || pos.j!=pos.prevj) {
  47. table[pos.i][pos.j] += table[pos.previ][pos.prevj];
  48. table[pos.i][pos.j] %= m;
  49. }
  50. //if (pos.i == 2 && pos.j == 2) cout << pos.previ << " " << pos.prevj << endl;
  51. if (states[pos.i][pos.j]) continue;
  52. n.i = pos.i+1;
  53. n.j = pos.j;
  54. n.previ = pos.i;
  55. n.prevj = pos.j;
  56. q.push(n);
  57. n.i = pos.i;
  58. n.j = pos.j+1;
  59. q.push(n);
  60. states[pos.i][pos.j] = true;
  61. }
  62. }
  63.  
  64. int main() {
  65. while (cin >> s) {
  66. len = s.length();
  67. for (int i = 0; i < len; i++) {
  68. for (int j = 0; j < len; j++) {
  69. table[i][j]=0;
  70. states[i][j] = false;
  71. }
  72. }
  73. table [0][0] = 1;
  74. bfs ();
  75. /*for (int i = 0; i < len; i++) {
  76. for (int j = 0; j < len; j++) {
  77. cout << table[i][j] << " ";
  78. }
  79. cout << endl;
  80. }*/
  81. cout << table [len/2][len/2] << endl;
  82. }
  83. return 0;
  84. }
  85.  
  86.