Разбор задачи acmp — Фермер

  • В этой теме 0 ответов, 1 участник, последнее обновление 3 месяца, 4 недели назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6340
      @admin

      Условие задачи взято с сайта acmp.ru (Время: 2 сек. Память: 16 Мб Сложность: 46%):

      Фермер решил на своем квадратном участке земли вспахать пашню квадратной формы максимальной площади, т.к. он посчитал, что именно квадратная форма пашни наиболее удобна для обработки. Но на его участке присутствуют деревья и хозяйственные постройки, которые он никуда не хочет переносить, а так же иные места, не пригодные для пашни. Для удобства он составил квадратную карту местности N×N в форме матрицы и пометил нулями непригодные для пашни зоны, в остальные зоны он поставил единицу.

      Необходимо помочь фермеру определить максимальную площадь пашни.

      Входные данные

      В первой строке входного файла INPUT.TXT записано единственное натуральное число N (1 ≤ N ≤ 1000) – длина стороны квадратного участка фермы. Далее, следует N строк, в каждой из которых находится последовательность (без пробелов) нулей и единиц, описывающих ферму.

      Выходные данные

      В выходной файл OUTPUT.TXT необходимо вывести максимально возможную площадь пашни.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 7
      1101101
      1111110
      1011100
      0011100
      1000010
      1100111
      1001110
      9

      Разбор решения задачи

      Также рекомендую такой набор входных данных:

      INPUT.TXT OUTPUT.TXT
      2 6
      0 1 1 0 0 0
      1 1 1 1 1 1
      1 1 1 1 0 0
      0 1 1 1 1 1
      0 1 0 1 1 0
      0 1 0 1 0 1
      9

      Нужно заметить, что фермеру нужно поле именно квадратной (а не прямоугольной) формы — это упрощает задачу. Для приведенного примера существует два оптимальных поля — это хорошо видно на картинке:

      Как найти такие поля? — для начала, чтобы убедиться что мы верно поняли задачу и форматы входных/выходных данных, можно написать неэффективное решение, заключающееся в переборе всех возможных полей. Для этого, из каждой клетки с координатами i-j попробуем построить поля всех возможных размеров (начиная с n, заканчивая нулем):

      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      //! проверяет можно ли на поле \a field построить пашню
      //! с левым вехним углом в позиции \a corner
      //! размера \a m
      bool can_build(vector<vector<int>> &field, std::pair<int, int> corner, int m) {
        if (field.size() < m + max(corner.first, corner.second))
          return false;
      
        for(int i = 0; i < m; i++) {
          for(int j = 0; j < m; j++) {
            if (0 == field[i + corner.first][j+corner.second])
              return false;
          }
        }
        return true;
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n;
        ifst >> n;
      
        vector<vector<int>> field(n, vector <int>(n));
      
        for(int i = 0; i < n; i++) {
          for(int j = 0; j < n; j++) {
            char c;
            ifst >> c;
            field[i][j] = (c == '1');
          }
        }
      
        for(int m = n; m > 0; --m) {
          for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
              if (can_build(field, make_pair(i, j), m)) {
                ofst << m*m;
                return 0;
              }
            }
          }
        }
      
        ofst << 0;
      }

      Это очень медленное решение, его вычислительную сложность можно оценить как O(n^5), так как для каждой из n^2 клеток мы перебираем n возможных размеров и для каждого из них выполняем проверку, которая тоже требует O(n^2) операций. Чтобы найти более оптиимальное решение, нужно заметить, что большее по размеру поле с координатами верхнего левого угла (i, j) обязательно включает в себя меньшее поле — с координатами (i+1, j+1). На приведенной ниже картинке показано как одно из полей 3×3 включает в себя меньшие поля, внутри каждой клетки записан максимальный размер поля, которое можно построить с этой клеткой в верхнем левом углу:

      Теперь мы можем заметить, что если сторона меньшего поля равна m, то у большего — не более m+1. За счет этого, мы можем значительно ускорить решение — для каждой клетки можно перебирать не все возможные размеры полей, а от 1 до m+1:

        int field_max = field[0][0];
        for(int i = 0; i < n; i++) {
          if (true == field[i][n-1] || true == field[n-1][i]) {
            field_max = 1;
            break;
          }
        }
      
        for(int i = n-2; i >= 0; --i) {
          for(int j = n-2; j >= 0; --j) {
            int pivot = field[i+1][j+1];
      
            for(int m = pivot+1; m > 0; --m) {
              if (can_build(field, make_pair(i,j), m)) {
                field[i][j] = m;
                field_max = max(field_max, m);
                break;
              }
            }
          }
        }

      Вычислительная сложность такого решения можно оценить как O(n^2 * m^3), где m — наибольший размер поля (m <= n). Это несколько лучше, но не достаточно. В самом деле, сейчас при проверке возможности построения в клетке (i, j) квадрата со стороной m мы перебираем m^2 ячеек. Однако, если внутрь этого квадрата вложен квадрат со стороной k, k^2 ячеек уже обработаны и гарантированы свободны для засева. Нам остается проверить лишь одну строку и один столбец. На рисунке зеленым цветом выделена текущая клетка, красным — обрабатываемые клетки. Слева — визуализация объема работы для предыщущего варианта программы, а справа — следующего:

      Вычислительная сложность такого решения — O(n^2 * m^2), изменилась лишь функция проверки возможности построения квадрата:

      bool can_build(vector<vector<int>> &field, std::pair<int, int> corner, int m) {
        if (field.size() < m + max(corner.first, corner.second))
          return false;
      
        for(int i = 0; i < m; i++) {
          if (0 == field[i+corner.first][corner.second])
            return false;
          if (0 == field[corner.first][i+corner.second])
            return false;
        }
        return true;
      }

      Такое решение проходит все тесты на сайте, однако возможны варианты входных данных, когда оно сработает очень медленно. В решении мы уже применили динамическое программирование, когда вместо повторной обработки всех ячеек квадрата решили использовать полученный ранее результат. Однако, до сих пор мы использовали данные только от одной ячейки, расположенной по диагонали, но стоит посмотреть какие ячейки уже гарантированно обработаны:

      Красным цветом выделена текущая ячейка, серым — еще не обработанные, а зеленым — обработанные. Суть более оптимального решения заключается в том, что мы можем использовать не только данные ячейки (i+1, j+1), но и данные из ячеек (i, j+1) и (i+1, i):

      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n;
        ifst >> n;
      
        vector<vector<int>> field(n, vector <int>(n));
      
        for(int i = 0; i < n; i++) {
          for(int j = 0; j < n; j++) {
            char c;
            ifst >> c;
            field[i][j] = (c == '1');
          }
        }
      
        int field_max = field[0][0];
        for(int i = 0; i < n; i++) {
          if (true == field[i][n-1] || true == field[n-1][i]) {
            field_max = 1;
            break;
          }
        }
      
        for(int i = n-2; i >= 0; --i) {
          for(int j = n-2; j >= 0; --j) {
            if (field[i][j]) {
              field[i][j] = min(field[i+1][j], field[i][j+1]);
              field[i][j] = min(field[i][j], field[i+1][j+1]);
              field[i][j]++;
            }
      
            field_max = max(field[i][j], field_max);
          }
        }
      
        ofst << field_max*field_max;
      }

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.