Ayuda backtracking (programacion avanzada)

[extremoo]

Hola a todos les comento, estoy trabajando con backtracking y estoy algo complicado con el codigo del problema por ejemplo me pide que lea los numeros indicados en una linea separados por espacio, y lea desde teclado una matriz de esas dimensiones, la matriz contiene las siguientes caracteristicas :
" ." (punto) si no hay cosas
"*" (arterisco) que corresponde a una rueda
"I" (i mayuscula) que corresponde a un motor que gira en sentido horario. Ojo si al lado de la I encuentra un * ese arterisco gira en sentido contrario ya que lo hace girar la I

mi codigo es el siguiente hasta ahora puedo leer la matriz sin problemas hasta encontrar que el usuario ingrese 0 0 y termine.

Código C++:

#include <iostream>
using namespace std;
 
void llenar(char **s,int posx, int posy)
{
//aqui defino posiciones  q revisar la de iz de I, la de derecha, arriba,abajo, (arriba der y abajo iz). para aplicar backtraking
    s[0][0] = posx   ;
    s[0][1] = posy -1;
 
    s[1][0] = posx   ;
    s[1][1] = posy +1;
 
    s[2][0] = posx +1;
    s[2][1] = posy -1;
 
    s[3][0] = posx -1;
    s[3][1] = posy +1;
 
    s[4][0] = posx -1;
    s[4][1] = posy   ;
 
    s[5][0] = posx +1;
    s[5][1] = posy   ;
}
 
void mostrar(char **t, int n, int m) 
{ 
    for(int i=0 ; i< n; i++) 
    { 
     for(int j=0; j < m ; j++) 
     { 
      cout<<""<<t[i][j]; 
     } 
     cout<<endl; 
    } 
}
 
int main (int argc, char** argv)
{
  int R,C;
  char **arr;
  cin >>R;
  cin >>C;  
  while( R != 0  &&  C != 0 )
  {
    arr = new char*[R];
    for(int i= 0; i <R ; i++)
    {
        arr[i] = new char[C];
        for(int j = 0; j < C ; j++)
        {
        cin>>arr[i][j];
        }
    }
  cout<<endl;
// backtraking(arr,R,C,i,j);
  mostrar(arr,R,C);    
  cin >>R;
  cin >>C;
  }    
return 0;
}
 

En estos momentos necesito recorrer nuevamente la matriz guardada hasta encontrar una I y colocarle un "(" parentesis y la rueda que hace girar la I colocarle un ")" de esta forma.

Ejemplo visual
---------------------
para in
-----------
3 3
...
.I*
...
-----------
para out para in
______
...
.()
...