Depth First Traversal ( DFS ) on a 2D array/2D grid

Given a 2D grid[][] which has a dimension of n*M, find the depth first search traversal of the given 2D array

Examples1 :

Input: grid[][] = {{-1, 2, 3}, 

                             {0, 9, 8}, 

                             {1, 0, 1}}

Output: -1 2 3 8 1 0 9 0 1

Explanation: The sequence of traversal of matrix elements using DFS is -1, 2, 3, 8, 1, 0, 9, 0, 1.

Examples 2 :

Input: grid[][] = {{1, 2, 3}, {5, 6, 7}, {9, 10, 11}}

Output: 1 2 3 7 11 10 6 5 9

method  :

take starting cell coordinates as (0, 0).

use visited 2d array of dimensions n*m with all values as 0, which is used to mark the visited cells.

here we have to only move to four directions up ,right ,down ,left from a cell 

example (x, y) is a cell whose adjacent cells (x – 1, y), (x, y + 1), (x + 1, y), (x, y – 1) needs to be traversed then it can be done using the direction vectors (-1, 0), (0, 1), (1, 0), (0, -1) in the up, right, down and left order.

check if the cell coordinates are valid or not, i.e lies within the boundaries of the given matrix and are unvisited or not. and then call dfs again from that cell

c++ implementation:

#include<bits/stdc++.h>
using namespace std;

int n ;int m;
int vis[1001][1001];
int grid[1001][1001];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

void dfs(int x,int y)
{
    cout<<grid[x][y]<<" ";
    vis[x][y]=1;
for (int i=0;i<4;i++)
{ int u=x+dx[i];int v=y+dy[i];
if(u>=0 && u<n && v>=0 && v<m && vis[u][v]==0 )
        dfs(u,v);
}
}

int main()
{	
		cin >> n >> m;
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				cin >> grid[i][j];
				vis[i][j]=0;
			}
		}
	
		dfs(0,0);	

	return 0;
}