Advertisement
Guest User

Untitled

a guest
Nov 20th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS 0
  2. #include <iostream>
  3. #include <math.h>
  4. using namespace std;
  5.  
  6. int n, m, a[1000][1000], b[1000][1000], c[1000][1000];
  7.  
  8. void horse ( int i , int j ){
  9. if (i + 1 < n && j + 2 < m) {
  10. if (c[i + 1][j + 2] == a[i + 1][j + 2] || a[i + 1][j + 2] + c[i][j] > c[i + 1][j + 2]){
  11. c[i + 1][j + 2] = a[i + 1][j + 2] + c[i][j];
  12. horse(i + 1, j + 2);
  13. }
  14. b[i + 1][j + 2] = 1;
  15. }
  16. if (i + 2 < n && j + 1 < m) {
  17. if (c[i + 2][j + 1] == a[i + 2][j + 1] || a[i + 2][j + 1] + c[i][j] > c[i + 2][j + 1]){
  18. c[i + 2][j + 1] = a[i + 2][j + 1] + c[i][j];
  19. horse(i + 2, j + 1);
  20. }
  21. b[i + 2][j + 1] = 1;
  22. }
  23. if (i - 1 >= 0 && j + 2 < m) {
  24. if (c[i - 1][j + 2] == a[i - 1][j + 2] || a[i - 1][j + 2] + c[i][j] > c[i - 1][j + 2]){
  25. c[i - 1][j + 2] = a[i - 1][j + 2] + c[i][j];
  26. horse(i - 1, j + 2);
  27. }
  28. b[i - 1][j + 2] = 1;
  29. }
  30. if (i + 2 < n && j - 1 >= 0) {
  31. if (c[i + 2][j - 1] == a[i + 2][j - 1] || a[i + 2][j - 1] + c[i][j] > c[i + 2][j - 1]){
  32. c[i + 2][j - 1] = a[i + 2][j - 1] + c[i][j];
  33. horse(i + 2, j - 1);
  34. }
  35. b[i + 2][j - 1] = 1;
  36. }
  37. }
  38.  
  39.  
  40. int main() {
  41. freopen("input.txt", "r", stdin);
  42. freopen("output.txt", "w", stdout);
  43. cin >> n >> m;
  44. for (int i = 0; i < n; i++){
  45. for (int j = 0; j < m; j++){
  46. cin >> a[i][j];
  47. c[i][j] = a[i][j];
  48. b[i][j] = 0;
  49. }
  50. }
  51. if (n > 2 || m > 2){
  52. horse(0 , 0);
  53. }
  54. if ( b[n-1][m-1] == 1 )
  55. cout << c[n-1][m-1];
  56. else
  57. cout << "-";
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement