fork(30) download
copy 
  1. #include <stdio.h>
  2.  
  3. const int MAX   = 50;
  4. const int MAX_D = 4;
  5. const int DOWN = 0, LEFT = 1, RIGHT = 2;
  6.  
  7. int G[MAX][MAX];
  8. int M[MAX][MAX][MAX * MAX][3];
  9. int n, m;
  10.  
  11. int max (int a, int b) { return a > b ? a : b; }
  12.  
  13. int f(int i, int j, int p, int d) {
  14. 	if (i == n || j == n || j < 0 || p == m)
  15. 		return 0;
  16.  
  17. 	if (M[i][j][p][d] != -1) return M[i][j][p][d];
  18. 	int ret = 0;
  19. 	if (d == DOWN) {
  20. 		ret = max(ret, f(i + 1, j, p + 1, DOWN));
  21. 		ret = max(ret, f(i, j - 1, p + 1, RIGHT));
  22. 		ret = max(ret, f(i, j + 1, p + 1, LEFT));
  23. 	} else if (d == LEFT) {
  24. 		ret = max(ret, f(i + 1, j, p + 1, DOWN));
  25. 		ret = max(ret, f(i, j + 1, p + 1, LEFT));
  26. 	} else {
  27. 		ret = max(ret, f(i + 1, j, p + 1, DOWN));
  28. 		ret = max(ret, f(i, j - 1, p + 1, RIGHT));
  29. 	}
  30. 	return M[i][j][p][d] = ret + G[i][j];
  31. }		
  32.  
  33. int main()
  34. {
  35. 	for (int i = 0; i < MAX; i++) {
  36. 		for (int j = 0; j < MAX; j++) {
  37. 			for (int p = 0; p < MAX * MAX; p++)
  38. 				for (int d = 0; d < MAX_D; d++)
  39. 					M[i][j][p][d] = -1;
  40. 			G[i][j] = 0;
  41. 		}
  42. 	}
  43.  
  44. 	scanf ("%d %d", &n, &m);
  45. 	for (int i = 0; i < n; i++)
  46. 		for (int j = 0; j < n; j++)
  47. 			scanf ("%d", &G[i][j]);
  48.  
  49. 	printf ("%d\n", f(0, 0, 0, DOWN));
  50. 	return 0;
  51. }
Success #stdin #stdout 0.07s 75968KB
comments (?)
stdin
copy 
3 7
1 1 1
0 1 1
1 1 0
stdout
copy 
7
https://ideone.com/tbH1j
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

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!