Helping solve geometry - has no idea

Question

I am preparing for a programming competition, and I would like to know how I can solve this problem. I guess this is a geometry problem, and it seems like I can't figure out how to solve it.

There he is:

There is a courtyard in which there are wolves and sheep. There are also blocks in the yard that do not allow passage. Wolves are represented by "w" and sheep with "s", and blocks with "#", and the space in which everyone can move is ".". Thus, a possible input would look like this:

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

The 2 digits above the yard are rows x columns.

As you can see, different types of sectors can be formed in the yard. Here are two sectors:

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

There is a wolf in the first, and a sheep in the second. Since they are located in two different sectors (i.e. the Wolf cannot reach the sheep), he cannot eat it. If they were in the same sector, the wolf would eat sheep.

My question for you is this: given input like the above, how should I calculate how many sheep will survive? How can I imagine a “yard” in C ++? What should the algorithm look like? Are there any materials for understanding such problems and problems?

Any help is appreciated. Thanks in advance.

Answer 1

What you are looking for is to find the related components of the graph, then you just need to count the number of wolves and sheep in each of them.

 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; 

The runtime and memory usage are optimal for O (row x columns).

Please note that the code is not verified, but I believe this should work.

Answer 2

This problem basically consists in finding related subgraphs (aka components) for a given graph.

You can solve the problem by presenting each "non-blocking" coordinate as a node graph, linking 2 adjacent coordinates on the graph. Then find connected subgraphs using BFS (or any other algorithm suitable for the theme - I am sure that any web page or Wiki on graphic algos will have a list of different algorithms.

Once you have your subgraphs, just find which subgraphs have zero wolves (by determining which subgraph will contain each wolf coordination) and count the sheep in these subgraphs.

Hope this is enough to get you started.

Answer 3

A simple approach would be to fill the fill , starting with each wolf. You can assume that each wolf will move (flood) the points around it. After you fill the filling, starting from all points, the remaining sheep will survive.

In your example:

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

will be filled before:

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

(I used f for the filled space) and the algorithm will stop, so s saved.

Answer 4

perhaps think of the yard as a group of sectors. when creating a sector, if it has a wolf, delete all the sheep. Now the only task is a sector that looks much more manageable.

Answer 5

Consider the use of flood flood algorithms.

Answer 6

Not like geometry to me. I would solve it using Flood fill

Fill all areas with a unique number. Then, for each number on which you filled the area, you will find out how many sheep and how many wolves are adjacent to this number. The only surviving sheep are those that are adjacent to the number k, to which the wolves are not attached.

You can think of a matrix in C ++ as a matrix of characters: char A [maxrows] [maxcols]. However, to use the fill fill, I would use the ints matrix, because you may have more areas than the maximum char value.

Answer 7

Is this time limited competition? For example, where does your assessment depend on the number of programs being solved at a given time?

For them, I would recommend a simple approach based on two things:

• Presenting data as a 2D array

• Determine when sheep and wolves exchange sectors by looking at the connection using something like the fill filling algorithm from each wolf. I would advise starting with the wolves and “killing” the sheep when you reach them. After you do this for each wolf, all the remaining sheep in the data structure will survive.

The key to time-limited competitions is the development of a simple solution that is quickly programmed. Modern computers are very fast. Do not think about geometric algorithms, if you do not need to process huge amounts of data, just think about how I can easily calculate the problem when solving the problem.

While I was thinking about this, some other people were offering flooding, so this is somewhat redundant.