CODEWITHSUNDEEP
c#algorithmrecursion
Bennett Yeo
Bennett Yeo

Reputation: 829

Grid exploring algorithm with move constraints

Lately I've been stuck on an algorithm for "exploring a grid". I want to paint all moves that are valid within a certain part of a grid based on a starting square that could be anywhere on the grid. My original plan was to use recursive split off in 4 directions marking grids until it either reached a boundary or the move limit. An exploring "branch" cannot move diagonally:

*note: arrows do not represent occurrence in stack, they are there for visualizing the concept of the algorithm

enter image description here

private void Explore(byte moves, byte row, char col) {
        if (row >= Grid[0].Count || col >= Grid.Count || row + col + 2 > moves) {//var < 0 handled b/c byte b = 0; (byte)(b-1) == 255
            return;
        }
        Grid[row][col].color = ...;//mark it

        if (Grid[row + 1][col + 1] == notVisited) Explore((byte) (moves - 1), (byte)(row + 1), (char) (col + 1));
        if (Grid[row - 1][col + 1]== notVisited) Explore((byte)(moves - 1), (byte)(row - 1), (char) (col + 1));
        if (Grid[row - 1][col - 1] == notVisited) Explore((byte)(moves - 1), (byte)(row - 1), (char) (col - 1));
        if (Grid[row + 1][col - 1] == notVisited) Explore((byte)(moves - 1), (byte)(row + 1), (char) (col - 1));
    }

I know this algorithm doesn't work b/c I did a quick runnable sample here where the algorithm gets stuck between values until it triggers a Runtime error.

So at this point:

  1. Is recursion still a possibility (switch to iterative)?

  2. Is there a better alternative algorithm to this problem?

  3. Is my algorithm close, but needs a few tweaks?

Upvotes: 1

Views: 1062

Answers (2)

Blubber
Blubber

Reputation: 1483

The idea for searching should work fine, but the reason the code does not work is because it is checking for the diagonals. 

if (Grid[row + 1][col + 1] == notVisited)
if (Grid[row - 1][col + 1]== notVisited) 
if (Grid[row - 1][col - 1] == notVisited) 
if (Grid[row + 1][col - 1] == notVisited)

I think you mean: 

if (Grid[row + 1][col] == notVisited)
if (Grid[row - 1][col]== notVisited) 
if (Grid[row][col + 1] == notVisited) 
if (Grid[row][col - 1] == notVisited)

For the questions:

1: Recursion is fine. Iterative would be faster, but it won't make too much of a difference.

2: There are probably tons different ways to do it, but the current method should be fine.

3: Besides changing those four conditionals, this condition 

|| row + col + 2 > moves)

might cause the program to act strangely depending on where it is put. The moves parameter will not be the same for all recursion paths, so it's likely that most times the program will paint the entire grid. Other than that, the program should run fine.

Upvotes: 1

H W
H W

Reputation: 2586

You seem to be looking to implement depth-first search. The wiki article even provides some pseudo code which you can use to implement the algorithm.

Note that this will mark all reachable squares, but will not print out all (redundant) moves unless you modify the algorithm.

Upvotes: 1

Related Questions