Flood fill for a tile map without using List.Contains

Unity Engine
,
1

Hello, I have an array Tiles[Tile, Tile] which I use as a map and I need to write a flood fill to select valid tiles to spawn characters and items into; I would like to avoid using List.Contains to check if a Tile has been already evaluated due to poor performance, so I think I need a way to tag those tiles, maybe a boolean?
I thought about two solutions:

1- Create an array of bools that mirrors the map (same width and height) and then use tiles’ coordinates to access and tag the positions inside the array; considering the map can go up to 300*300, is that a good idea? Would that create a lot of garbage collecting?
This is the code:

public Tile GetValidTile_FlagMap(Tile tile, Pathfinder.TileEvaluator tileEvaluator)
    {
        bool[,] flagMap = new bool[Width, Height];
        Queue<Tile> queue = new Queue<Tile>();
        queue.Enqueue(tile);
        while (queue.Count > 0)
        {
            Tile t = queue.Dequeue();
            if (tileEvaluator(t))
            {
                return t;
            }
            flagMap[t.X, t.Y] = true;
            Tile[] neighbours = t.GetNeighbours(false);
            foreach (Tile neighbour in neighbours)
            {
                if (neighbour != null && flagMap[neighbour.X, neighbour.Y] == false)
                {
                    queue.Enqueue(neighbour);
                }
            }
        }
        return null;
    }

2- Add a bool inside the Tile class and use that to tag the tiles, add the tagged tiles to a list and then reset those tiles’ data before returning the value; It should be faster then using List.Contains but would that produce less garbage than the other function? Also I have doubt, is it possible for two functions to access the data at the same time creating bugs? It shouldn’t happen right?
The code would be something like this:

public Tile GetValidTile_FlagTile(Tile tile, Pathfinder.TileEvaluator tileEvaluator)
    {
        List<Tile> evaluatedTiles = new List<Tile>();
        Queue<Tile> queue = new Queue<Tile>();
        queue.Enqueue(tile);
        while (queue.Count > 0)
        {
            Tile t = queue.Dequeue();
            if (tileEvaluator(t))
            {
                foreach (Tile evaluatedTile in evaluatedTiles)
                {
                    evaluatedTile.isEvaluated = false;
                }
                return t;
            }
            t.isEvaluated = true;
            evaluatedTiles.Add(t);
            Tile[] neighbours = t.GetNeighbours(false);
            foreach (Tile neighbour in neighbours)
            {
                if (neighbour != null && neighbour.isEvaluated == false)
                {
                    queue.Enqueue(neighbour);
                }
            }
        }
        return null;
    }

Thanks.

2

I would just use a HashSet to keep track of already-evaluated tiles. It’s much faster for this access pattern than a list. HashSets were designed to be very efficient for the Contains operation.

public Tile GetValidTile_FlagTile(Tile tile, Pathfinder.TileEvaluator tileEvaluator)
    {
        HashSet<Tile> evaluatedTiles = new HashSet<Tile>();
        Queue<Tile> queue = new Queue<Tile>();
        queue.Enqueue(tile);
        while (queue.Count > 0)
        {
            Tile t = queue.Dequeue();
            if (tileEvaluator(t))
            {
                foreach (Tile evaluatedTile in evaluatedTiles)
                {
                    evaluatedTile.isEvaluated = false;
                }
                return t;
            }
            evaluatedTiles.Add(t);
            Tile[] neighbours = t.GetNeighbours(false);
            foreach (Tile neighbour in neighbours)
            {
                if (neighbour != null && !evaluatedTiles.Contains(neighbor))
                {
                    queue.Enqueue(neighbour);
                }
            }
        }
        return null;
    }
3

Isn’t tagging tiles still faster than this? Also isn’t HashSet.Contains slower than List.Contains when the HashSet is small?
What about using a pool of Arrays? I could get one, tag what I want, then send it back and reinitialised it; would this create less garbage collecting? Thanks.