Advertisement
Josif_tepe

Untitled

Aug 4th, 2023
859
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.78 KB | None | 0 0
  1. #define _CRF_SECURE_NO_WARNINGS
  2. #define _CRT_SECURE_NO_DEPRECATE
  3.  
  4. #include <stdio.h>
  5.  
  6. const int MaxN = 210;
  7. const int MaxM = 210;
  8. const int MaxK = 55;
  9.  
  10. int n, m, k;
  11. char map[MaxN][MaxM];
  12. char map2[MaxN][MaxN];
  13.  
  14. short column[MaxM][MaxN][MaxK];
  15. short row[MaxN][MaxM][MaxK];
  16.  
  17. short left[MaxN][MaxK];
  18. short right[MaxN][MaxK];
  19.  
  20. short max(short a, short b) { return a > b ? a : b; }
  21. short min(short a, short b) { return a < b ? a : b; }
  22.  
  23. void CalculateRow(int m, char *map, int _k, short row[MaxN][MaxK])
  24. {
  25.     // left
  26.     left[0][0] = map[0] == '.';
  27.     for (int i = 1; i < m; ++i) {
  28.         if (map[i] == '*') left[i][0] = 0;
  29.         else left[i][0] = left[i - 1][0] + 1;
  30.     }
  31.  
  32.     for (int k = 1; k <= _k; ++k) {
  33.         left[0][k] = 1;
  34.         for (int i = 1; i < m; ++i) {
  35.             if (map[i] == '*') left[i][k] = left[i - 1][k - 1] + 1;
  36.             else left[i][k] = left[i - 1][k] + 1;
  37.         }
  38.     }
  39.  
  40.     // right
  41.     right[m - 1][0] = map[m - 1] == '.';
  42.     for (int i = m - 2; i >= 0; --i) {
  43.         if (map[i] == '*') right[i][0] = 0;
  44.         else right[i][0] = right[i + 1][0] + 1;
  45.     }
  46.  
  47.     for (int k = 1; k <= _k; ++k) {
  48.         right[m - 1][k] = 1;
  49.         for (int i = m - 2; i >= 0; --i) {
  50.             if (map[i] == '*') right[i][k] = right[i + 1][k - 1] + 1;
  51.             else right[i][k] = right[i + 1][k] + 1;
  52.         }
  53.     }
  54.  
  55.     // merge
  56.     for (int i = 0; i < m; ++i) {
  57.         if (map[i] == '*') row[i][0] = 0;
  58.         else row[i][0] = left[i][0] + right[i][0] - 1;
  59.     }
  60.  
  61.     for (int k = 1; k <= _k; ++k) {
  62.         row[0][k] = right[0][k];
  63.         row[m - 1][k] = left[m - 1][k];
  64.  
  65.         for (int i = 1; i < m - 1; ++i) {
  66.             int newK = k;
  67.             if (map[i] == '*') newK = k - 1;
  68.  
  69.             for (int leftK = 0; leftK <= newK; ++leftK) {
  70.                 int rightK = newK - leftK;
  71.                 row[i][k] = max( row[i][k], left[i - 1][leftK] + right[i + 1][rightK] + 1 );
  72.             }
  73.         }
  74.  
  75.     }
  76. }
  77.  
  78. int main()
  79. {
  80.     scanf("%d%d%d", &n, &m, &k);
  81.     for (int i = 0; i < n; ++i) {
  82.         scanf("%s", map[i]);
  83.     }
  84.  
  85.     // rotate matrix (columns to rows)
  86.     for (int i = 0; i < n; ++i) {
  87.         for (int j = 0; j < m; ++j)
  88.             map2[j][i] = map[i][j];
  89.     }
  90.  
  91.     for (int i = 0; i < n; ++i)
  92.         CalculateRow(m, map[i], k, row[i]);
  93.     for (int i = 0; i < m; ++i)
  94.         CalculateRow(n, map2[i], k, column[i]);
  95.  
  96.     short oldret = -1;
  97.     short retR = -1;
  98.     short retC = -1;
  99.     short rowObstacles = -1;
  100.     short columnObstacles = -1;
  101.  
  102.     short ret = 0;
  103.     for (int i = 0; i < n; ++i) {
  104.         for (int j = 0; j < m; ++j) {
  105.             for (int rowK = 0; rowK <= k; ++rowK) {
  106.                 int columnK = k - rowK;
  107.  
  108.                 if (map[i][j] == '*') {
  109.                     if (rowK != 0)
  110.                         ret = max(ret, row[i][j][rowK] + column[j][i][columnK + 1] - 1);
  111.                     if (columnK != 0)
  112.                         ret = max(ret, row[i][j][rowK + 1] + column[j][i][columnK] - 1);
  113.                 }
  114.                 else {
  115.                     ret = max(ret, row[i][j][rowK] + column[j][i][columnK] - 1);
  116.                 }
  117.  
  118.                 if (oldret < ret) {
  119.                     oldret = ret;
  120.                     retR = i;
  121.                     retC = j;
  122.                     rowObstacles = rowK;
  123.                     columnObstacles = columnK;
  124.                 }
  125.             }
  126.         }
  127.     }
  128.  
  129.     printf("%d\n", ret);
  130.  
  131.     /*
  132.     printf("Row = %d\n", retR);
  133.     printf("Column = %d\n", retC);
  134.     printf("Mapa[%d][%d] = %c\n", retR, retC, map[retR][retC]);
  135.     printf("Row obstacles = %d\n", rowObstacles);
  136.     printf("Column obstacles = %d\n", columnObstacles);
  137.     */
  138.  
  139.     return 0;
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement