[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 3454
  • Last Modified:

Depth-first search 2d array

Hello

I’m programming in c++

I have a 2d array of ints
Int map[10][10];

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.
Please provide some sample code


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

Thank you
0
funvill
Asked:
funvill
  • 3
  • 3
1 Solution
 
sunnycoderCommented:
Hi funvill,

Is this your homework assignment ?

Sunnycoder
0
 
funvillAuthor Commented:
0
 
sunnycoderCommented:
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
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
funvillAuthor 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
http://www.boost.org/libs/graph/doc/breadth_first_search.html

Thank you for your time
0
 
funvillAuthor 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[4][2] = { {  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[1][1].m_passable = false;
      map[1][2].m_passable = false;
      map[1][3].m_passable = false;
      map[2][1].m_passable = false;
      map[2][3].m_passable = false;
      map[3][1].m_passable = false;
      map[3][2].m_passable = false;
      map[3][3].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("[0]");
                  }
            }
            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][0];
                ay = pos.y + DIRTABLE[dir][1];

                // 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("[0]");
                                                }
                                          }
                                          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;
}
0
 
NetminderCommented:
User resolved; points (50) refunded and question closed.

Netminder
Site Admin
0

Featured Post

Prep for the ITIL® Foundation Certification Exam

December’s Course of the Month is now available! Enroll to learn ITIL® Foundation best practices for delivering IT services effectively and efficiently.

  • 3
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now