Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- int main( ) {
- std::ios_base::sync_with_stdio(0);
- std::cin.tie(0);
- std::cout.tie(0);
- int n;
- std::cin >> n;
- std::vector<int> pos[n];
- char mapa[n][n];
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- std::cin >> mapa[i][j];
- if (mapa[i][j] == '*') {
- pos[i].push_back(j);
- }
- }
- }
- int costo[n + 1][n] = { };
- for (int i = n - 1; i >= 0; --i) {
- for (int j = 0; j < n; ++j) {
- if (mapa[i][j] != '#') {
- costo[i][j] += costo[i + 1][j];
- }
- }
- for (auto it : pos[i]) {
- int ini = it, fin = it + 1;
- for (; ini >= 0 && mapa[i][ini] != '#'; --ini) {
- costo[i][ini] += 1;
- }
- for (; fin < n && mapa[i][fin] != '#'; ++fin) {
- costo[i][fin] += 1;
- }
- int max = std::max_element(costo[i][ini], costo[i][fin]);
- for (int a = ini; a <= fin; ++a) {
- costo[i][a] = max;
- }
- }
- }
- std::cout << costo[0][0] << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement