fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int mod = (int) 1e9 + 7;
  5.  
  6. void addmod(int& res, int add) {
  7. 	res += add;
  8. 	if (res >= mod) res -= mod;
  9. }
  10.  
  11. int n;
  12. char a[505][505];
  13. int dp1[505][505];
  14. int dp2[505][505];
  15.  
  16. int main() {
  17. 	scanf("%d", &n);
  18. 	for (int i = 0; i < n; i++) {
  19. 		scanf("%s", a[i]);
  20. 	}
  21.  
  22. 	dp1[0][0] = 1;
  23. 	for (int len = 0; len < n - 1; len++) {
  24. 		for (int i = 0; i <= len + 1; i++) {
  25. 			for (int j = 0; j <= len + 1; j++) {
  26. 				dp2[i][j] = 0;
  27. 			}
  28. 		}
  29.  
  30. 		for (int i = 0; i <= len; i++) {
  31. 			for (int j = 0; j <= len; j++) {
  32. 				//cout << "check i="<<i<<" j="<<j<<" dp[i][j]="<<dp1[i][j]<<endl;
  33. 				int ix = i;
  34. 				int iy = len - i;
  35. 				int jx = n - 1 - j;
  36. 				int jy = n - 1 - (len - j);
  37. 				if (a[ix + 1][iy] == a[jx - 1][jy]) {
  38. 					addmod(dp2[i + 1][j + 1], dp1[i][j]);
  39. 				}
  40. 				if (a[ix + 1][iy] == a[jx][jy - 1]) {
  41. 					addmod(dp2[i + 1][j], dp1[i][j]);
  42. 				}
  43. 				if (a[ix][iy + 1] == a[jx - 1][jy]) {
  44. 					addmod(dp2[i][j + 1], dp1[i][j]);
  45. 				}
  46. 				if (a[ix][iy + 1] == a[jx][jy - 1]) {
  47. 					addmod(dp2[i][j], dp1[i][j]);
  48. 				}
  49. 			}
  50. 		}
  51.  
  52. 		//cout << "len = " << len << endl;
  53. 		for (int i = 0; i <= len + 1; i++) {
  54. 			for (int j = 0; j <= len + 1; j++) {
  55. 				dp1[i][j] = dp2[i][j];
  56. 				//cout << dp1[i][j] << " ";
  57. 			}
  58. 			//cout << endl;
  59. 		}
  60. 	}
  61.  
  62. 	int ans = 0;
  63. 	for (int i = 0; i <= n; i++) {
  64. 		addmod(ans, dp1[i][n - 1 - i]);
  65. 	}
  66.  
  67. 	printf("%d\n", ans);
  68. }
  69.  
Success #stdin #stdout 0s 5712KB
comments (?)
stdin
copy 
4
ABCD
BXZX
CDXB
WCBA
stdout
copy 
12
https://ideone.com/sj0BWb
dp problem two paths from corners http://c...content-available-to-author-only...s.com/blog/entry/50169
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!