Художник

В этой задаче необходимо понять, что координаты закрашиваемых прямоугольников определяются не координатами ячеек, а координатами сетки, т.е. левая верхняя координата имеет значение (0,0) в то время как правая нижняя - (w,h). Это следует из примеров, первый из которых представлен на рисунке справа, где видно, что действительно 18 клеток таблицы не закрашены.

Данная задача решается "в лоб". Можно определить матрицу a[1..n][1..m] и пошагово считывать координаты противоположных вершин прямоугольника и сразу же заполнять единицами этот прямоугольник в матрице. Предварительно матрицу необходимо обнулить. По завершении процесса можно подсчитать число оставшихся нулей в матрице, это и будет ответом на задачу. Максимальное число простых операций может быть равно 50 000 000. Несмотря на такое, казалось бы огромное число решение задачи укладывается в 1 секунду. Дело в том, что проводимые операции - это заполнение элементов массива числами, которые выполняются очень быстро. Если бы столько же раз нам нужно было выполнить серию умножений, то мы вряд ли смогли бы рассчитывать на успех.

Приведем пример решения данной задачи на алгоритмическом языке:

  int a[1..100][1..100]={0...0};

  read(w,h,n);
  for i=1..n{
    read(x1,y1,x2,y2);
    for y=y1+1..y2{
      for x=x1+1..x2{
        a[y][x]=1;
      }
    }
  }
  c=0;
  for y=1..h{
    for x=1..w{ 
      c=c+1-a[y][x];
    }
  }
  write(c);

[Обсуждение] [Все попытки] [Задача]