Task - algorithm problem

Hello, I need help solving a problem I have encountered.
We have a map NxM filled with '.' ,'#' and one 'x'.
'.' are passable fields
'#' are blocks
'x' is the starting position.
So you can move from 'x' up, down, left or right.
The problem is to find how much fields you can capture if you can't go on '#'
and fields where you've already been.
So the output needs to be a string of ('w','s','a','d') which simulates your movement.
I have tried with dfs but it's to slow, do you have any ideas?
Take a look at this thread for ideas on how to explore a map.
http://www.cplusplus.com/forum/beginner/189792/#msg920772
Yes, that's preety nice, but that is not the problem.
If you have a map like this:
4 4
.#..
.x#.
....
....

Then the solution is:
assdwdsdwwwa

The map can then be represented as this:
.#xx
xx#x
xxxx
xxxx
So the (1,1) field is not captured.
that is not the problem.

I didn't say that thread was the perfect solution to your problem. It does however show you how to explore a map using recursion.

If you want to track directions traveled to explore the map, use a stack. As you recurse down, record the direction traveled in the stack. As you exit recursive levels, pop the stack. When you reach the goal, the contents of the stack will have the record of the directions traveled to get there.
I think that you didn't understand the problem, I know how to explore a map, but recursion here is too much slow.
Topic archived. No new replies allowed.