We help IT Professionals succeed at work.

# Depth-first search 2d array

on
Medium Priority
6,998 Views
Hello

I’m programming in c++

I have a 2d array of ints
Int map;

Each element has value of 1 or 0
1 is passable
0 is not passable

I have 2 locations on the array
(2, 2) and (5, 5)

I want to make sure that the two positions are reachable by each other.

i will give more points if you can show me how to do the same thing with a
A* search

Thank you
Comment
Watch Question

## View Solution Only

CERTIFIED EXPERT
Top Expert 2006

Commented:
Hi funvill,

Is this your homework assignment ?

Sunnycoder
CERTIFIED EXPERT
Top Expert 2006

Commented:
Ok ... here we go

step 1 : you need an entry point into the maze ... let us assume that it is 0,0

step 2 : now imagine that you have a tree of possible moves ... your initial position will be at the root of this tree ...
All possible positions after the next move would the children of a given node in the tree

e.g. take a simplistic matrix
E  1  0
0  1  1
1  1  0

E denotes the entry point .... now your root is 0,0
Assuming that diagonal moves are disallowed, you can only go to 0,1 in this case ... so your tree would look like
0,0
|
|
0,1
from 0,1 you can go to 1,1 only ... all other moves are disallowed ... so your search tree becomes
0,0
|
|
0,1
|
|
1,1

from here you have two options to follow ... either you can go to 1,2 or 2,1 .. thus your search tree becomes

0,0
|
|
0,1
|
|
1,1
/    \
/      \
1,2     2,1
and so on so forth ... In such a tree you need to find if there is a particular node present along any path ... If it is present, then it is reachable ... To find the node, you need to search the tree

You can use either DFS or BFS or A* to search the tree ... http://www.ics.uci.edu/~eppstein/161/960215.html gives a good explanation of BFS and DFS ...

Note that the search space I constructed above was a bit simple ... I did not take into account the nodes which have already been seen/processed ... To apply this kind of thing to your problem you need to keep a track of nodes already processed (the difference between DFS for a tree and DFS for a graph)

I think this should be good enough to get you started ....

Sunnycoder

Commented:
I know the theory behind all of these search patterns that’s not what I asked for.

I was just looking for a simple solution so I wouldn’t have to think so much (not having much spare time any more)

But if I don’t get a suitable answer by the weekend I guess I will just use a boost lib

CERTIFIED EXPERT
Top Expert 2006

Commented:

Commented:
still not what i asked for :(
i spent 30min that i didn't have today and answered my own question

#include <queue>

#define MAP_SIZE_X      5
#define MAP_SIZE_Y      5

#define GOAL_X      3
#define GOAL_Y      4

#define START_X      0
#define START_Y      4

class cell
{
public:

bool m_passable; ;
bool m_marked;
};

class Coordinate
{
public:
int x;
int y;
float heuristic;
};

const int DIRTABLE = { {  0, -1 },    // N
{  1,  0 },    // E
{  0,  1 },    // S
{ -1,  0 }};    // W

int main()
{

cell map[MAP_SIZE_X][MAP_SIZE_Y];
int ax, ay;
int x, y;

int moves  = 0;
bool found = false ;

/// Make a map
// =================

/******
X012345
0000000
1011100
2010100
3011100
4@00X00
5000000
******/
// 0 = Passable
// 1 = Not passable
// @ = Current location
// X = Goal

/// set all to true
// =================
for (x = 0 ; x < MAP_SIZE_X; x++)
{
for (y = 0 ; y < MAP_SIZE_Y; y++)
{
map[x][y].m_passable = true;
map[x][y].m_marked   = false ;
}
}

map.m_passable = false;
map.m_passable = false;
map.m_passable = false;
map.m_passable = false;
map.m_passable = false;
map.m_passable = false;
map.m_passable = false;
map.m_passable = false;

std::queue<Coordinate> Q;

// Add the start to the que
Coordinate pos;

pos.x = START_X;
pos.y = START_Y;
pos.heuristic = 0.0f;

Q.push(pos);

/// Print the map
// ===============
for (x = 0 ; x < MAP_SIZE_X; x++)
{
for (y = 0 ; y < MAP_SIZE_Y; y++)
{
if ( map[x][y].m_marked )
{
printf("[X]");
}
else
{
printf("");
}
}
printf("\n");
}

// start the main loop
while( Q.size() != 0 )
{
printf("=== Start of loop === \n");

// pull the first cell off the queue and process it.
pos.x = Q.front().x;
pos.y = Q.front().y;
Q.pop();

printf("X=[%d] Y=[%d]\n",pos.x , pos.y);

// check to see if its allready checked
if ( map[pos.x][pos.y].m_marked == false )
{
// status
printf("X=[%d] Y=[%d] New node\n",pos.x , pos.y);
// mark the cell as it is pulled off the queue.
map[pos.x][pos.y].m_marked = true ;

// we are at our gole then quit
if (pos.x == GOAL_X && pos.y == GOAL_Y)
{
printf("X=[%d] Y=[%d] We are at our goal\n",pos.x , pos.y);
found = true ;
break;
}

// loop through each direction.
for( int dir = 0; dir < 4; dir++ )
{
// retrieve the coordinates of the current adjacent cell
ax = pos.x + DIRTABLE[dir];
ay = pos.y + DIRTABLE[dir];

// check to see if the adjacent cell is a valid index,
// passable
if( ax >= 0                  && ay >= 0 &&
ax < MAP_SIZE_X && ay < MAP_SIZE_Y)
{
if ( map[ax][ay].m_passable == true )
{
printf("\tChecking X=[%d] Y=[%d]\n", ax , ay);
// add the new ones to the que
pos.x = ax ;
pos.y = ay ;
Q.push(pos);

/// Print the map
// ===============
for (x = 0 ; x < MAP_SIZE_X; x++)
{
for (y = 0 ; y < MAP_SIZE_Y; y++)
{
if ( ax == x && ay == y )
{
printf("[@]");
}
else if ( map[x][y].m_marked )
{
printf("[X]");
}
else
{
printf("");
}
}
printf("\n");
}

moves++;

}
else
{
printf("\tNot passable X=[%d] Y=[%d]\n", ax , ay);
}
}
else
{
printf("\tOut of bounds X=[%d] Y=[%d]\n", ax , ay);
}
}
}
else
{
// we have allready been here
printf("X=[%d] Y=[%d] is allready marked\n",pos.x , pos.y);

}

}

printf("\n\n==============================\n");

if ( found )
{
printf("Found in %d moves\n", moves);
}
else
{
printf("Did not find out goal\n");
}
printf("End of program\n");

return 0;
}
Commented:
Unlock this solution and get a sample of our free trial.
(No credit card required)
Unlock the solution to this question.