Advertisement
Josif_tepe

Untitled

Aug 4th, 2023
822
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <stack>
  8. using namespace std;
  9. typedef long long ll;
  10. const int maxn = 222;
  11. const int maxk = 55;
  12. char mat[maxn][maxn];
  13. int L[maxn][maxn][maxk];
  14. int R[maxn][maxn][maxk];
  15. int up[maxn][maxn][maxk];
  16. int down[maxn][maxn][maxk];
  17. int rows[maxn][maxn][maxk];
  18. int cols[maxn][maxn][maxk];
  19. int main() {
  20.     ios_base::sync_with_stdio(false);
  21.     int n, m, k;
  22.     cin >> n >> m >> k;
  23.     for(int i = 0; i < n; i++) {
  24.         for(int j = 0; j < m; j++) {
  25.             cin >> mat[i][j];
  26.         }
  27.     }
  28.    
  29.     for(int x = 0; x <= k; x++) {
  30.         for(int i = 0; i < n; i++) {
  31.             for(int j = 0; j < m; j++) {
  32.                 int tmp_x = x;
  33.                 if(mat[i][j] == '*') {
  34.                     tmp_x--;
  35.                 }
  36.                
  37.                 if(tmp_x < 0) {
  38.                     up[i][j][x] = 0;
  39.                 }
  40.                 else {
  41.                     up[i][j][x] = 1;
  42.                     if(i > 0) {
  43.                         up[i][j][x] += up[i - 1][j][tmp_x];
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.     }
  49.     for(int x = 0; x <= k; x++) {
  50.         for(int i = n - 1; i >= 0; i--) {
  51.             for(int j = m - 1; j >= 0; j--) {
  52.                 int tmp_x = x;
  53.                 if(mat[i][j] == '*') {
  54.                     tmp_x--;
  55.                 }
  56.                 if(tmp_x < 0) {
  57.                     down[i][j][x] = 0;
  58.                 }
  59.                 else {
  60.                     down[i][j][x] = 1;
  61.                     if(i + 1 < n) {
  62.                         down[i][j][x] += down[i + 1][j][tmp_x];
  63.                     }
  64.                 }
  65.             }
  66.         }
  67.     }
  68.     for(int x = 0; x <= k; x++) {
  69.         for(int i = 0; i < n; i++) {
  70.             for(int j = 0; j < m; j++) {
  71.                 int tmp_x = x;
  72.                 if(mat[i][j] == '*') {
  73.                     tmp_x--;
  74.                 }
  75.                 if(tmp_x < 0) {
  76.                     L[i][j][x] = 0;
  77.                 }
  78.                 else {
  79.                     L[i][j][x] = 1;
  80.                     if(j > 0) {
  81.                         L[i][j][x] += L[i][j - 1][tmp_x];
  82.                     }
  83.                 }
  84.             }
  85.         }
  86.     }
  87.     for(int x = 0; x <= k; x++) {
  88.         for(int i = n - 1; i >= 0; i--) {
  89.             for(int j = m - 1; j >= 0; j--) {
  90.                 int tmp_x = x;
  91.                 if(mat[i][j] == '*') {
  92.                     tmp_x--;
  93.                 }
  94.                 if(tmp_x < 0) {
  95.                     R[i][j][x] = 0;
  96.                 }
  97.                 else {
  98.                     R[i][j][x] = 1;
  99.                     if(j + 1 < m) {
  100.                         R[i][j][x] += R[i][j + 1][tmp_x];
  101.                     }
  102.                 }
  103.             }
  104.         }
  105.     }
  106.    
  107.     for(int i = 0; i < n; i++) {
  108.         for(int j = 0; j < m; j++) {
  109.             for(int x = 0; x <= k; x++) {
  110.                 rows[i][j][x] = 0;
  111.                 int tmp_x = x;
  112.                 if(mat[i][j] == '*') {
  113.                     tmp_x--;
  114.                 }
  115.                 if(tmp_x >= 0) {
  116.                     for(int y = 0; y <= tmp_x; y++) {
  117.                         int tmp_y = tmp_x - y;
  118.                         int sum = 1;
  119.                         if(i + 1 < n) {
  120.                             sum += down[i + 1][j][tmp_y];
  121.                         }
  122.                         if(i > 0) {
  123.                             sum += up[i - 1][j][y];
  124.                         }
  125.                         rows[i][j][x] = max(rows[i][j][x], sum);
  126.                     }
  127.                 }
  128.             }
  129.         }
  130.     }
  131.     for(int i = 0; i < n; i++) {
  132.         for(int j = 0; j < m; j++) {
  133.             for(int x = 0; x <= k; x++) {
  134.                 cols[i][j][x] = 0;
  135.                 int tmp_x = x;
  136.                 if(mat[i][j] == '*') {
  137.                     tmp_x--;
  138.                 }
  139.                 if(tmp_x >= 0) {
  140.                     for(int y = 0; y <= tmp_x; y++) {
  141.                         int tmp_y = tmp_x - y;
  142.                         int sum = 1;
  143.                         if(j + 1 < m) {
  144.                             sum += R[i][j + 1][y];
  145.                         }
  146.                         if(j > 0) {
  147.                             sum += R[i][j - 1][tmp_y];
  148.                         }
  149.                         cols[i][j][x] = max(cols[i][j][x], sum);
  150.                     }
  151.                 }
  152.             }
  153.         }
  154.     }
  155.     int result= 0;
  156.     for(int i = 0; i < n; i++) {
  157.         for(int j = 0; j < m; j++) {
  158.             int tmp_x = k;
  159.             int obstacle = 0;
  160.             if(mat[i][j] == '*') {
  161.                 tmp_x--;
  162.                 obstacle = 1;
  163.             }
  164.             if(tmp_x >= 0) {
  165.                 for(int x = 0; x <= tmp_x; x++) {
  166.                     int y = tmp_x - x;
  167.                     int r_tmp = x + obstacle;
  168.                     int c_tmp = y + obstacle;
  169.                     result = max(result, rows[i][j][r_tmp] + cols[i][j][c_tmp] - 1);
  170.                 }
  171.             }
  172.         }
  173.     }
  174.     cout << result - 1 << endl;
  175.     return 0;
  176. }
  177.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement