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

Question

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

Здесь:

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

2 цифры над двором - это строки x столбцов.

Как вы можете видеть, этим могут быть сформированы участки разного вида во дворе. Вот два сектора:

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

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

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

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

Answer 1

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

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 2

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

Answer 3

Эта проблема в основном заключается в поиске connected sub-graphs (aka components) для данного графика.

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

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

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

Answer 4

Рассмотрит с помощью логики flood filling алгоритмов.

Answer 5

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

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

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

Answer 6

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

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

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

бы набить:

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

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

Answer 7

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

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

• представляют данные в виде 2D массива

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

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

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