The flood algorithm isn't that hard to implement. When you meet a dead end, or already explored path, you backup to the last place that you had a choice and take the untrodden path. If you have already trodden that path then backup some more. When implementing the flood algorithm for graphics, you have to keep a software stack to keep track of where you had a choice, with a maze you can reverse until you have an adjoining square with a unknown wall status and follow down that path.
As for storing the maze, you should be able to fit it in the internal memory. Assuming the maze is 16*16 squares and you store the top and left wall status as 2 bits each you will need 16*16*2*2 = 1024 bits or 128 bytes. I suggest 2 bits per wall so you have 00=unknown 10 = no wall and 11 = wall.
I'm not familiar with the AT chips so can't help with example code.
Mike.