Advertisement
Guest User

Untitled

a guest
May 30th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. int nbCols, nbLignes;
  9. int grille[500][500];
  10. int plusMax[500][500];
  11. const int dirs[4][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };
  12.  
  13. const int INF = 2000000000;
  14.  
  15. bool estBord(int i, int j)
  16. {
  17. return (i == 0 || i == nbLignes-1 || j == 0 || j == nbCols-1);
  18. }
  19.  
  20. int main()
  21. {
  22. scanf("%d%d", &nbCols, &nbLignes);
  23.  
  24. for(int i = 0; i < nbLignes; i++)
  25. {
  26. for(int j = 0; j < nbCols; j++)
  27. {
  28. scanf("%d", &grille[i][j]);
  29. plusMax[i][j] = INF;
  30. if(estBord(i, j)) //bords
  31. plusMax[i][j] = grille[i][j];
  32. }
  33. }
  34.  
  35. for(int k = 0; k < 30; k++) //hum, + ou - ? on va mettre un grand truc pour pas de pb et que รงa passe ><
  36. for(int i = 0; i < nbLignes; i++)
  37. {
  38. for(int j = 0; j < nbCols; j++)
  39. {
  40. if(estBord(i, j))
  41. continue;
  42.  
  43. int valBordMin = INF;
  44.  
  45. for(int d = 0; d < 4; d++)
  46. {
  47. int x = j + dirs[d][0];
  48. int y = i + dirs[d][1];
  49.  
  50. if(x >= 0 && x < nbCols && y >= 0 && y < nbLignes)
  51. valBordMin = min(valBordMin, plusMax[y][x]);
  52. }
  53.  
  54. plusMax[i][j] = std::max(grille[i][j], valBordMin);
  55. }
  56. }
  57.  
  58. int total = 0;
  59.  
  60. for(int i = 0; i < nbLignes; i++)
  61. for(int j = 0; j < nbCols; j++)
  62. total+=plusMax[i][j]-grille[i][j];
  63.  
  64. printf("%d\n", total);
  65.  
  66. return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement