How can i generate random maps for a .txt Pacman in C language?

everyone! I have the task of design a simple pacman game in C language using threads and semaphores. We're allowed to use ncurses.h library for the development. I'm also supposed to load a wired map into a .txt file who gotta look like this in order to start the game:

 *******************
*. . . . . . . . . .*
*.**.**.*****.**.**.*
*.**.**.*****.**.**.*
*. . . . . . . . . .*
*.**.**.*****.**.**.*
*.**.**.*****.**.**.*
*. . . . . . . . . .*
 *******************

My question is: How can i randomly generates valid maps (ig, the random map need to have '*' all around the border of the matrix as limit, cannot be a blocked map, ie, pacman and the ghost can move all across the map and there's always at least one path to connect the entire map, it also needs to generate walls which are the '**' inside the gamezone, dots that pacman will eat and spaces between them and allow a NxN size for the matrix) I don't have a clue of where should i start and should i learn to be able to do this! Any advices? Thanks