Hola buenas
Quería ver si me podían ayudar porque tengo duda de como hacer que mi matriz valla checando cada casilla, hasta que encuentre alguna casilla vacía coloque alguna letra (Ejemplo: M) y hasta hay finalice mi recorrido por la matriz

Pues recorres hasta encontrar una casilla vacia agregas y sales 
Algo asi mira

bool casilla_vacia=false;
 
for(int i=0;i<MAX && !casilla_vacia;i++){
	for(int j=0;j<MAX && !casilla_vacia;j++){
		//Esto si fuera un arreglo de carateres, todo depende lo que vaya a contener tu matriz, si es de punteros entonces el valor vacio es NULL;
		if(matriz[i][j]==""){
			matriz[i][j]=nuevo_dato;
			casilla_vacia=true;
		}
	}
}