document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. /************************************************
  2. Programmer : Muhammad Azri bin Jasni @ Abdul Rani
  3. Program    : project euler problem 11.cpp
  4. Link       : http://projecteuler.net/problem=11
  5. Description: Wrong answer
  6. Note       : -
  7. *************************************************
  8. In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
  9.  
  10. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
  11. 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
  12. 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
  13. 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
  14. 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
  15. 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
  16. 32 98 81 28 64 23 67 10 [26] 38 40 67 59 54 70 66 18 38 64 70
  17. 67 26 20 68 02 62 12 20 95 [63] 94 39 63 08 40 91 66 49 94 21
  18. 24 55 58 05 66 73 99 26 97 17 [78] 78 96 83 14 88 34 89 63 72
  19. 21 36 23 09 75 00 76 44 20 45 35 [14] 00 61 33 97 34 31 33 95
  20. 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
  21. 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
  22. 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
  23. 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
  24. 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
  25. 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
  26. 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
  27. 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
  28. 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
  29. 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
  30.  
  31. The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
  32.  
  33. What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?
  34. ************************************************/
  35. /*
  36. Draft
  37. 1. put in 2-dimensional array
  38. 2. get max product of 4 adjacent numbers for diogonally, horizontaly and vertically (three for-loop)
  39. 3. test with small sample:
  40. 08 02 22 97        
  41. 49 49 99 40
  42. 81 49 31 73
  43. 52 70 95 23
  44.  
  45. 08 09 are octal form, cant be used for int?? huh?
  46.  
  47. horizontal and vertical was done using trial and error... so I don\'t remember
  48.  
  49. diagonal test
  50. [0][0] [1][1] [2][2] [3][3] , [0][1] [1][2] [2][3] [3][4]
  51. [1][0] [2][1] [3][2] [4][3] , [1][1] [2][2] [3][3] [4][4]
  52. for (int i=0;i<max-3;i++)
  53.     for (int j=0;j<max-3;j++)
  54.         [i][j]*[i+1][j+1]*[i+2][j+2]*[i+3][j+3]
  55.        
  56. we may reduce process by identify 0. bcoz 0 will result in zero, so can skip instantly if want
  57. */
  58. #include <iostream>
  59. using namespace std;
  60. bool checkZero(int);
  61. int main ()
  62. {
  63.     const int max = 20;
  64.     int maxProduct = 0;//greatest product
  65.     int product = 1;
  66.     //initialize array
  67.     int numbers [max][max] =
  68.     {
  69.         { 8,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91, 8},
  70.         {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00},
  71.         {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65},
  72.         {52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91},
  73.         {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
  74.         {24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50},
  75.         {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
  76.         {67,26,20,68,02,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
  77.         {24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
  78.         {21,36,23, 9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95},
  79.         {78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14, 9,53,56,92},
  80.         {16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57},
  81.         {86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58},
  82.         {19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40},
  83.         {04,52, 8,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66},
  84.         {88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69},
  85.         {04,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36},
  86.         {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16},
  87.         {20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54},
  88.         {01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48}
  89.     };
  90.     //horizontal
  91.     for (int i=0; i<(max); i++)
  92.     {
  93.         for (int j=0; j<(max-3); j++)
  94.         {
  95.             if (checkZero(numbers[i][j]))
  96.                continue;
  97.            
  98.             product = numbers[i][j] * numbers[i][j+1] * numbers[i][j+2]  * numbers[i][j+3];
  99.             //cout << numbers[i][j] << "*" << numbers[i][j+1] << "*" << numbers[i][j+2]<< "*" << numbers[i][j+3] << "=" << product <<endl;//test
  100.             if (product > maxProduct)
  101.                maxProduct = product;
  102.         }
  103.     }
  104.     //cout << "===========" << endl; //test
  105.     //vertical
  106.     for (int j=0; j<(max); j++)
  107.     {
  108.         for (int i=0; i<(max-3); i++)
  109.         {
  110.             if (checkZero(numbers[i][j]))
  111.                continue;
  112.             product = numbers[i][j] * numbers[i+1][j] * numbers[i+2][j]  * numbers[i+3][j];
  113.             //cout << numbers[i][j] << "*" << numbers[i+1][j] << "*" << numbers[i+2][j] << "*" << numbers[i+3][j] << "=" << product <<endl;//test
  114.             if (product > maxProduct)
  115.                maxProduct = product;
  116.         }
  117.     }
  118.     //cout << "===========" << endl; //test
  119.     //diagonal
  120.     for (int i=0; i<(max-3); i++)
  121.     {
  122.         for (int j=0; j<(max-3); j++)
  123.         {
  124.             if (checkZero(numbers[i][j]))
  125.                continue;
  126.             product = numbers[i][j] * numbers[i+1][j+1] * numbers[i+2][j+2]  * numbers[i+3][j+3];
  127.             //cout << numbers[i][j] << "*" << numbers[i+1][j+1] << "*" << numbers[i+2][j+2] << "*" << numbers[i+3][j+3] << "=" << product <<endl;//test
  128.             if (product > maxProduct)
  129.                maxProduct = product;
  130.         }
  131.     }
  132.    // cout << "===========" << endl; //test
  133.     cout << "maxProduct = " << maxProduct << endl;
  134.     //system("pause");
  135.     return 0;
  136. }
  137.  
  138. bool checkZero(int a)
  139. {
  140.      if (a==0)
  141.         return true;
  142.      else
  143.          return false;
  144. }
');