Advertisement
AlejandroGY

Untitled

Dec 9th, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. int main( ) {
  6.    std::ios_base::sync_with_stdio(0);
  7.    std::cin.tie(0);
  8.    std::cout.tie(0);
  9.  
  10.    int n;
  11.    std::cin >> n;
  12.  
  13.    std::vector<int> pos[n];
  14.    char mapa[n][n];
  15.    for (int i = 0; i < n; ++i) {
  16.       for (int j = 0; j < n; ++j) {
  17.          std::cin >> mapa[i][j];
  18.          if (mapa[i][j] == '*') {
  19.             pos[i].push_back(j);
  20.          }
  21.       }
  22.    }
  23.  
  24.    int costo[n + 1][n] = { };
  25.    for (int i = n - 1; i >= 0; --i) {
  26.  
  27.       for (int j = 0; j < n; ++j) {
  28.          if (mapa[i][j] != '#') {
  29.             costo[i][j] += costo[i + 1][j];
  30.          }
  31.       }
  32.  
  33.       for (auto it : pos[i]) {
  34.          int ini = it, fin = it + 1;
  35.          for (; ini >= 0 && mapa[i][ini] != '#'; --ini) {
  36.             costo[i][ini] += 1;
  37.          }
  38.          for (; fin < n && mapa[i][fin] != '#'; ++fin) {
  39.             costo[i][fin] += 1;
  40.          }
  41.          int max = std::max_element(costo[i][ini], costo[i][fin]);
  42.          for (int a = ini; a <= fin; ++a) {
  43.             costo[i][a] = max;
  44.          }
  45.       }
  46.    }
  47.    std::cout << costo[0][0] << "\n";
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement