Помогите с проблемой геометрии - не имею понятия

Question

Я готовлюсь к соревнованиям по программированию и хотел бы узнать, как я могу решить эту проблему. Я предполагаю, что это проблема геометрии, и, похоже, я не могу понять, как ее решить.

Вот оно:

Есть двор, в котором есть волки и овцы. Во дворе есть также блоки, которые не позволяют пройти. Волки обозначены буквой «w», а овцы - «s», в то время как блоки обозначены «#», а пространство, в котором каждый может двигаться, - «.» , Таким образом, возможный ввод будет выглядеть так:

8 8
.######.
#..s...#
#.####.#
#.#w.#.#
#.#.s#s#
#s.##..#
#.w..w.#
.######.

2 числа над двором - строки х столбцов.

Как видите, таким образом во дворе могут образовываться сектора разного типа. Вот два сектора:

####
#.w#
####
#s.#

В первом есть волк, а во втором - овца. Поскольку они расположены в двух разных секторах (то есть волк не может добраться до овец), он не может есть это. Если бы они были в одном секторе, волк съел бы овец.

Мой вопрос к вам таков: учитывая данные, подобные приведенным выше, как мне рассчитать, сколько овец выживет? Как я могу представить «двор» в C ++? Как должен выглядеть алгоритм? Есть ли материалы для понимания подобных проблем и вопросов?

Любая помощь приветствуется. Заранее спасибо.

Answer 1

Эта проблема в основном является проблемой поиска связанных подграфов (или компонентов) для данного графа.

Вы можете решить проблему, представив каждую «неблокированную» координату в виде узла графа, связав 2 соседние координаты в графе. Затем найдите связанные подграфы с помощью BFS (или любого другого алгоритма, подходящего для данной темы - я уверен, что любая веб-страница или Wiki в графических алгоритмах будет иметь список различных алгоритмов для этого.

Когда у вас есть ваши подграфы, просто найдите, какие из подграфов имеют нулевых волков (определив, какой подграф содержит каждая координата волка), и подсчитайте овец в этих подграфах.

Надеюсь, этого достаточно для начала.

Answer 2

Простой подход - сделать заливку , начиная с каждого волка. Вы можете предположить, что каждый волк будет перемещать (заливать) точки вокруг него. После заливки, начиная со всех точек, все оставшиеся овцы выживут.

В вашем примере:

####
#.w#
####
#s.#

заполнится до:

####
#fw#
####
#s.#

(я использовал f для заполненного пространства), и алгоритм остановится, поэтому s выживет.

Answer 3

То, что вы ищете здесь, - это найти связанные компоненты графика, тогда вам просто нужно посчитать количество волков и овец в каждом из них.

using namespace std;

int w, h;
cin >> w >> h;
vector<string> grid(h);
for (int i = 0; i < h; ++i)
  cin >> grid[i];

vector< vector<bool> > seen(h, vector<bool>(w, false));
int survived = 0;
const int mx[] = {-1, 0, 1, 0}, my[] = {0, -1, 0, 1};

for (int i = 0; i < h; ++i)
  for (int j = 0; j < w; ++j)
    if (!seen[i][j] && grid[i][j] != '#')
    {
      int sheep = 0, wolves = 0;
      typedef pair<int, int> point;
      stack<point> s;
      s.push(point(i, j));

      while (!s.empty())
      {
        point p = s.top();
        int x = p.first, y = p.second;
        if (grid[x][y] == 'w') wolves++;
        if (grid[x][y] == 's') sheep++;
        for (int k = 0; k < 4; ++k)
        {
          int x2 = x + mx[k], y2 = y + my[k];
          if (x2<0 || x2>=h || y2<0 || y2>=w) continue;
          if (grid[x2][y2] == '#' || seen[x2][y2]) continue;
          s.push(point(x2, y2));
        }
      }
      survived += max(0, sheep - wolves);
    }

cout << "Surviving sheep = " << survived << endl;

Время работы и использование памяти оптимально при O (строки x столбцы).

Обратите внимание, что код не проверен, но я считаю, что это должно работать.

Answer 4

Это ограниченное по времени соревнование? Например, где ваша оценка является функцией количества программ, решенных в данный момент времени?

Для этого я бы рекомендовал простой подход, основанный на двух вещах:

• Представляет данные в виде двумерного массива

• Определите, когда овцы и волки делят сектор, ища связь, используя что-то вроде алгоритма заполнения от каждого волка. Я бы порекомендовал начинать с волков и "убивать" овец, когда вы достигаете их. После того, как вы сделаете это для каждого волка, все оставшиеся овцы в структуре данных выживут.

Ключ в ограниченных по времени соревнованиях заключается в том, чтобы найти простое решение, которое можно быстро программировать. Современные компьютеры чрезвычайно быстры. Не думайте о геометрических алгоритмах, если вам не нужно обрабатывать большие наборы данных, просто подумайте, как я могу бросить вычисления на задачу, чтобы легко ее решить.

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

Answer 5

Не похоже на проблему геометрии для меня. Я бы решил это с помощью алгоритма Flood fill

Заполните каждую область уникальным номером. Затем для каждого числа, которым вы заполнили область, выясните, сколько овец и сколько волков находятся рядом с этим числом. Единственными выжившими овцами являются те, которые соседствуют с числом k, к которому не примыкают никакие волки.

Вы можете представить матрицу в C ++ как матрицу символов: char A [maxrows] [maxcols]. Однако, чтобы использовать заливку, я бы использовал матрицу целых чисел, потому что у вас может быть больше областей, чем максимальное значение символа.

Answer 6

Рассмотрите возможность использования логики алгоритмов заливки .

Answer 7

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