A “data structure problem” would involve more exotic data structures, usually of the kind the candidate has to implement themselves. For example, b-trees, heaps, skip lists, and so on.
The reason a lot of people don’t like custom data structure questions is that they come up rarely in most people’s jobs. Lists, structs and enums on the other hand are used everywhere. Your programming job will almost certainly require you to understand them.
But even then, while BFS would definitely work here, so would DFS and that’s simpler. A simple, unoptimised recursive DFS flood fill would be like 8 lines or something given by that stage you already have a function to reveal a cell. You just have to call it on all the adjacent cells. I don't see that as a data structure problem. You could argue it’s an algorithm problem, but it’s about as easy as those come.
Maybe I'm just thinking too much problem, overloaded my small attention brain and misread it. I wouldn't call Fizzbuzz data structure-y however.
I'm also mostly outsider looking in. Never worked at FAANG and working with YC companies, I come on much later and tends to be more keeping the lights on and stopping the duct tape rocket from exploding.