Help with geometry problem - don't have any idea

Question

I am preparing myself for programming competitions and i would like to know how can i solve this problem. I guess it's geometry problem, and it seems i can't get any ideas about solving it.

Here it is:

There is a yard in which there are wolves and sheep. In the yard there are also blocks which do not allow to pass. The wolves are represented with 'w' and the sheep with 's', while the blocks are with '#' and the space where everyone can move is '.' . So a possible input will look like:

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

The 2 numbers above the yard are rows x columns.

As you can see, by this there can be formed sectors of different kind in the yard. Here are two sectors:

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

In the first one there is a wolf and in the second a sheep. Because they are placed in two different sectors (i.e. the wolf can't get to the sheep), he can't eat it. If they were in a same sector, the wolf would eat the sheep.

My question for you is this: Given an input like the ones above, how should i calculate how many sheep will survive ? How can i represent the 'yard' in c++ ? How should the algorithm looks like ? Are there any materials for understanding similar problems and issues ?

Any help is appreciated. Thank you in advance.

Answer 1

maybe try thinking of the yard as a group of sectors. when creating a sector, if there is a wolf in it, remove all sheep. Now the only challenge is representing a sector, which seems much more manageable.

Answer 2

This problem is basically a problem of finding connected sub-graphs (aka components) for a given graph.

You can solve the problem by representing each "non-block" coordinate as a graph node, linking the 2 neighboring coordinates in a graph. Then find connected subgraphs using BFS (or any other algorithm suitable for the topic - I'm sure any web page or Wiki on graph algos will have a list of assorted algorithms on that.

Once you have your subgraphs, just find which subgraphs have zero wolves (by finding which subgraph each wolf coordinate is on), and count sheep in those subgraphs .

Hope this is enough for you to start.

Answer 3

Consider using the logic of flood filling algorithms.

Answer 4

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

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;

Running time and memory usage is optimal at O(rows x columns).

Note that code is untested, but I believe this should work.

Answer 5

Doesn't look like a geometry problem to me. I would solve it with the Flood fill algorithm

Fill every area with a unique number. Then, for every number you filled an area with, find out how many sheep and how many wolves are adjacent to that number. The only surviving sheep are those that are adjacent to a number k that no wolves are adjacent to.

You can represent the matrix in C++ as a matrix of chars: char A[maxrows][maxcols]. However, to use flood fill, I would use a matrix of ints, because you might have more areas than the max value of a char.

Answer 6

A simple approach would be to do a flood fill starting on each wolf. You can assume that each wolf will move (flood fill) the dots around him. After you flood fill starting from all the dots, any remaining sheep will survive.

In your example:

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

would fill to:

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

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

Answer 7

Is this a time-limited competition? E.g., one where your score is a function of the number of programs solved in a given time?

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

• Represent the data as a 2D array

• Determine when sheep and wolves share a sector by searching connectivity, using something like a flood-fill algorithm from each wolf. I would recommend starting from the wolves and "killing off" sheep when you reach them. After you do this for each wolf, any remaining sheep in the data structure survive.

The key in the time-limited competitions is to come up with a simple solution that's quick to program. Modern computers are extremely fast. Don't think about geometric algorithms unless you need to be able to handle vast data sets, just think how could I throw computation at the problem to solve it easily.

While I thought about this several other people suggested flood-filling, so this is somewhat redundant.