La mia mappa è diversa e non intacca in questo problema... credo che sia risolvibile facendo così:

codice:
   public static void mazeTraversal (int rig, int col)
	{
		matrice[rig][col] = 'x';
		//print();
      System.out.println(rig + " - "+col);
		
		if (rig == 4 && col == 11)
		{
			return;
		}		
		
		if (matrice[rig][col + 1] == '.')
			mazeTraversal (rig, col + 1);
		
		else if (matrice[rig + 1][col] == '.')
			mazeTraversal (rig + 1, col);
		
		else if (matrice[rig][col - 1] == '.')
			mazeTraversal (rig, col - 1);
			
		else if (matrice[rig - 1][col] == '.')
			mazeTraversal (rig - 1, col);
	

        	else if (matrice[rig][col + 1] == 'x')
			mazeTraversal (rig, col + 1);
		
		else if (matrice[rig + 1][col] == 'x')
			mazeTraversal (rig + 1, col);
		
		else if (matrice[rig][col - 1] == 'x')
			mazeTraversal (rig, col - 1);
			
		else if (matrice[rig - 1][col] == 'x')
			mazeTraversal (rig - 1, col);
	}
Prova