Mi sembra abbastanza ovvio che la matrice debba essere di char...

Potresti complicarti un pò la vita introducendo una struttura che definisca un nuovo tipo di dato...

In ogni caso il tutto dipende da come vuoi impostare la risoluzione del problema...