ulvis.paste.net

Paste Search Dynamic
Recent pastes
maxcoins
  1. define _CRT_SECURE_NO_WARNINGS
  2. #include<stdio.h>
  3.  
  4. int map[13][5], tempmap[13][5], M, maxcoins;
  5.  
  6. void detonate(int row)
  7. {
  8.         for(int i = row; i > row - 5; i--)
  9.         {
  10.                 for(int j = 0; j < 5; j++)
  11.                 {
  12.                         //      printf("here");
  13.                         if(map[i][j] == -1)
  14.                                 tempmap[i][j] = 0;
  15.                 }
  16.         }
  17. }
  18.  
  19. void undetonate(int row)
  20. {
  21.         for(int i = row; i > row - 5; i--)
  22.         {
  23.                 for(int j = 0; j < 5; j++)
  24.                 {
  25.                         //      printf("here");
  26.                         tempmap[i][j] = map[i][j];
  27.                 }
  28.         }
  29. }
  30.  
  31. void getmaxcoins(int r, int c, int coins)
  32. {
  33.         if(c<0 || c>4)
  34.                 return;
  35.         if(coins < 0 || r < 0)
  36.         {
  37.                 if(maxcoins < coins)
  38.                         maxcoins = coins;
  39.                 return;
  40.         }
  41.         getmaxcoins(r - 1, c, coins + tempmap[r - 1][c]);
  42.         getmaxcoins(r - 1, c - 1, coins + tempmap[r - 1][c - 1]);
  43.         getmaxcoins(r - 1, c + 1, coins + tempmap[r - 1][c + 1]);
  44. }
  45.  
  46. int main()
  47. {
  48. //      freopen("input.txt", "r", stdin);
  49.         int t, T;
  50.         scanf("%d", &T);
  51.         for(t = 1; t <= T; t++)
  52.         {
  53.                 scanf("%d", &M);
  54.                 maxcoins = 0;
  55.                 for(int i = 0; i < M; i++)
  56.                 {
  57.                         for(int j = 0; j < 5; j++)
  58.                         {
  59.                                 scanf("%d", &map[i][j]);
  60.                                 if(map[i][j] == 2)
  61.                                         map[i][j] = -1;
  62.                                 tempmap[i][j] = map[i][j];
  63.                         }
  64.                 }
  65.                 for(int i = M; i >0; i--)
  66.                 {
  67.                         detonate(i - 1);
  68.                         getmaxcoins(M, 2, 0);
  69.                         undetonate(i - 1);
  70.                 }
  71.                 if(maxcoins == 0)
  72.                         maxcoins = -1;
  73.                 printf("#%d %d\n", t, maxcoins);
  74.         }
  75.         return 0;
  76. }
Parsed in 0.014 seconds