Go to diff to previous submission
#include <algorithm> #include <cmath> #include<cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define REP(i,n) for ( int i = 0; i < (n); i++) #define FOR(i,a,b) for ( int i = (a); i <= (b); i++ ) #define FORD(i,a,b) for ( int i = (a); i>= (b); i-- ) #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl; struct node { int i,j; int previ, prevj; }; string s; queue<node> q; int m = 1000000,len; int table [1010][1010]; bool states [1010][1010]; void bfs () { node n, pos; n.i = n.j = 0; n.previ = n.prevj = 0; q.push(n); while (!q.empty()) { pos = q.front(); q.pop(); //cout << s[pos.i+pos.j-1] << endl; if (pos.previ < pos.i && s[pos.i+pos.j-1] == ')') continue; if (pos.prevj < pos.j && s[pos.i+pos.j-1] == '(') continue; if (2*pos.i > len) continue; if (pos.j > pos.i) continue; if (pos.i != pos.previ || pos.j!=pos.prevj) { table[pos.i][pos.j] += table[pos.previ][pos.prevj]; table[pos.i][pos.j] %= m; } //if (pos.i == 2 && pos.j == 2) cout << pos.previ << " " << pos.prevj << endl; if (states[pos.i][pos.j]) continue; n.i = pos.i+1; n.j = pos.j; n.previ = pos.i; n.prevj = pos.j; q.push(n); n.i = pos.i; n.j = pos.j+1; q.push(n); states[pos.i][pos.j] = true; } } int main() { while (cin >> s) { len = s.length(); for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { table[i][j]=0; states[i][j] = false; } } table [0][0] = 1; bfs (); /*for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { cout << table[i][j] << " "; } cout << endl; }*/ cout << table [len/2][len/2] << endl; } return 0; }
--- c5.s874.cteam027.fq.cpp.0.fq.cpp +++ c5.s879.cteam027.fq.cpp.0.fq.cpp @@ -27,5 +27,5 @@ string s; queue<node> q; -int m = 100000,len; +int m = 1000000,len; int table [1010][1010]; bool states [1010][1010];