Exponential time complexity during traversal

Question

I have tried learning and reading a lot about time complexity and I am sure it might sound pretty basic for most of the experts here(appologize for same), but still wanting to understand after doing a lot of research when I am not able to get hold on the concept

Matrix n*m.

case 1:

void traverse(int sr, int sc, int[][] mat, boolean[][] visited){
   if(sr<0 || sc<0 || sr>=mat.length || sc>=mat[0].length || visited[sr][sc] == true) return;
   
   visited[sr][sc]=true;  // not resetting state and it will be true for always
   traverse(sr, sc+1, mat, visited);
   traverse(sr, sc-1, mat, visited);
   traverse(sr+1, sc, mat, visited);
   traverse(sr-1, sc, mat, visited);
   
}

boolean[][] visited = new boolean[n][m];
for(int i=0; i<n; i++){
  for(int j=0; j<m; j++){
      if(!visited[i][j]){
          traverse(i, j, mat, visited);
      }
  }
}

time complexity:: O(n*m) -- what i can think of because for only first cell whole matrix will be traversed and as I am not resetting the state for all further i, j no traverse will occurr

case 2:

void traverse(int sr, int sc, int[][] mat, boolean[][] visited){
   if(sr<0 || sc<0 || sr>=mat.length || sc>=mat[0].length || visited[sr][sc] == true) return;
   
   visited[sr][sc]=true;  // resetting state
   traverse(sr, sc+1, mat, visited);
   traverse(sr, sc-1, mat, visited);
   traverse(sr+1, sc, mat, visited);
   traverse(sr-1, sc, mat, visited);
   visited[sr][sc]=false;
}

boolean[][] visited = new boolean[n][m];
for(int i=0; i<n; i++){
  for(int j=0; j<m; j++){
      if(!visited[i][j]){
          traverse(i,j, mat, visited);
      }
  }
}

time complexity:: O(n^2 * m^2) -- what i can think of because as I am resetting the state of visited[][] after one pass of j so for every new i & j whole matrix will be traversed.

If both of my above understanding is correct then wanted to understand when will the timecomplexity be 4^n*m.

does carrying visited[][] array is making a difference? one stack overflow question I have gone through and the expert who answered mentioned that visited[][] array is not getting cleared so time complexity is exponential else it would be O(V+E) of we are not clearing.

Please if someone could answer

1. I have gone through various youtube videos regarding timecomplexity
2. I have gone through book competitive programmers handbook
3. I have written matrix path traversal code and other code
4. I have gone through various stack overflow and other links