Review: the recursive Depth First Search algorithm

Recursive Depth First Search: 

   bool visited[N];

   void dfs(int i)
   {
      int j;

      visited[i] = true;  // Mark node i as "visited"

      /* ---------------------------------------------------------------
         We reached node i... Something wonderful may happen at i
         I print node i out - Replace with code that solves your problem
         --------------------------------------------------------------- */
      cout << i << endl;  // Debug use

      /* ---------------------------------------------------------------
         How you find nodes j will depend on how you represent the graph
         --------------------------------------------------------------- */
      for ( each node j that can be reached from node i )
      {
         if ( ! visited[j] )       
         {
            dfs(j);       // Visit node j
         }
      }
   }

Data used in the DFS algorithm

  


int  M, N;                      // Dimension of the room

int  grid[1002][1002];          // Magic values at each grid point
                                // in the room

bool visited[1002][1002];       // visited[x][y] = true, node (x,y) visited



Code to read the data in:

   cin >> M;
   cin >> N;

   // Read in magic values at grid and initialize visited[ ][ ]
   for ( int x = 1; x <= M; x++ )
      for ( int y = 1; y <= N; y++ )
      {
          cin >> grid[x][y];
          visited[x][y] = false;
      }

Writing the recursive Depth First Search algorithm

We need to adapt the DFS to our input data: 

   void dfs(int i)
   {
      int j;

      visited[i] = true;  // Mark node i as "visited"

      /* ---------------------------------------------------------------
         We reached node i... Something wonderful may happen at i
         I print node i out - Replace with code that solves your problem
         --------------------------------------------------------------- */
      cout << i << endl;  // Debug use

      /* ---------------------------------------------------------------
         How you find nodes j will depend on how you represent the graph
         --------------------------------------------------------------- */
      for ( each node j that can be reached from node i )
      {
         if ( ! visited[j] )       
         {
            dfs(j);       // Visit node j
         }
      }
   }

(1) the nodes are identified with 2 coordinates, e.g.: (x,y)

Writing the recursive Depth First Search algorithm

We need to adapt the DFS to our input data: 

   void dfs(int x, int y)
   {
      int i,j;

      visited[x][y] = true;        // Mark (x,y) as visited

      /* ---------------------------------------------------------------
         We reached node (x,y)... Something wonderful may happen at i
         I print node (x,y) out for now...
         --------------------------------------------------------------- */
      cout << x << y << endl;  // Debug use

      /* ---------------------------------------------------------------
         How you find nodes (i,j) depends on J5
         --------------------------------------------------------------- */
      for ( each node (i,j) that can be reached from node (x,y) )
      {
         if ( ! visited[i][j] )       
         {
            dfs(i,j);       // Visit node (i,j)
         }
      }
   }

(2) (i,j) can be reached from (x,y) if i*j = grid[x][y]

Writing the recursive Depth First Search algorithm

We need to adapt the DFS to our input data: 

   void dfs(int x, int y)
   {
      int i,j;

      visited[x][y] = true;        // Mark (x,y) as visited

      /* ---------------------------------------------------------------
         We reached node (x,y)... Something wonderful may happen at i
         I print node (x,y) out for now...
         --------------------------------------------------------------- */
      cout << x << y << endl;  // Debug use

      /* ---------------------------------------------------------------
         How you find nodes (i,j) depends on J5
         --------------------------------------------------------------- */
      for ( i = 1; i <= M; i++ )
      {  for ( j such that i*j == grid[x][y] ) {
         if ( ! visited[i][j] )       
         {
            dfs(i,j);       // Visit node (i,j)
         }                                        }
      }
   }

Note:   you do not need to search for j !! -- you can compute j !!!

Writing the recursive Depth First Search algorithm

We need to adapt the DFS to our input data: 

   void dfs(int x, int y)
   {
      int i,j;

      visited[x][y] = true;        // Mark (x,y) as visited

      /* ---------------------------------------------------------------
         We reached node (x,y)... Something wonderful may happen at i
         I print node (x,y) out for now...
         --------------------------------------------------------------- */
      cout << x << y << endl;  // Debug use

      /* ---------------------------------------------------------------
         How you find nodes (i,j) depends on J5
         --------------------------------------------------------------- */
      for ( i = 1; i <= M; i++ )
      {  j = grid[x][y] / i;

         if ( i*j == grid[x][y] && j <= N ) // j must be value: j <= N !!!
            if ( ! visited[i][j] ) 
               dfs(i,j);   // Visit node (i,j)
      }
   }

Question:   when will a wondeful thing happen ??   And what should we do then ???

Writing the recursive Depth First Search algorithm

We need to adapt the DFS to our input data: 

   void dfs(int x, int y)
   {
      int i,j;

      visited[x][y] = true;        // Mark (x,y) as visited

      if ( x == M && y == N )  // We reach the exit !
      {
         cout << "yes" << endl;
         exit(0);              // Quit program !!!
      }

      /* ---------------------------------------------------------------
         How you find nodes (i,j) depends on J5
         --------------------------------------------------------------- */
      for ( i = 1; i <= M; i++ )
      {  j = grid[x][y] / i;

         if ( i*j == grid[x][y] && j <= N ) // j must be value: j <= N !!!
            if ( ! visited[i][j] ) 
               dfs(i,j);   // Visit node (i,j)
      }
   }

Demo: CCC/2020/Progs/sol5.cc