fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int mod=1000000007;
  5. int n;
  6. char t[501][501];
  7. int	dp[501][501][501];
  8. int calc(int x1, int y1, int x2) {
  9. 	if(dp[x1][y1][x2]!=-1) return dp[x1][y1][x2];
  10. 	int y2=(n-1)-((x1+y1)-(n-1-x2));
  11. 	if(x1>x2 || y1>y2) return 0; //important optimalization!
  12. 	if(x1+y1==(n-1)) 
  13. 	{
  14. 		if(x1!=x2 || y1!=y2) return 0;
  15. 		else return 1;
  16. 	}
  17. 	if(t[x1][y1]!=t[x2][y2]) return 0;
  18.  
  19. 	long long ans=0;
  20. 	ans+=calc(x1+1,y1,x2);
  21. 	ans%=mod;
  22. 	ans+=calc(x1+1,y1,x2-1);
  23. 	ans%=mod;
  24. 	ans+=calc(x1,y1+1,x2);
  25. 	ans%=mod;
  26. 	ans+=calc(x1,y1+1,x2-1);
  27. 	ans%=mod;
  28.  
  29. 	return dp[x1][y1][x2]=ans;
  30. }
  31.  
  32. int main() {
  33. 	memset(dp, -1, sizeof dp);
  34. 	cin>>n;
  35. 	for(int i=0;i<n;++i)
  36. 		for(int j=0;j<n;++j)
  37. 			cin>>t[i][j];
  38.  
  39. 	cout<<calc(0,0,n-1)<<"\n";
  40. 	return 0;
  41. }
  42.  
Success #stdin #stdout 0.19s 494912KB
comments (?)
stdin 
4
ABCD
BXZX
CDXB
WCBA
stdout 
12
https://ideone.com/Py2OZ0
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!