1-Using a bidimensional array with the same size of the map. Each time you do a bfs, fill that array with 0. Then, mark with 1 the visited cells. 2-Use 2 arrays to store the visited positions.