Queue FIFO search speed up through the change of visited array?
Suppose 3 rooms each of which contains number 6 have been visited before any room the product of whose coordinates is 6 has been visited.
In the first version of your code, every room of the second kind will be put into the queue 3 times.
In the second version of your code, every room of the second kind will be put into the queue only 1 time (except possibly the room at (A,B), which will be put into the queue 2 times).
The difference between 3 times and 1 time is what slows down the first version. In general, there might be $m$ rooms of the first kind for the corresponding second kind. The appropriate average of $m$ in the test cases is substantially greater than 1. Hence you see the significant speedup from the first version to second version.

A good rule of thumb across all these kinds of searching problems is to try setting visited as soon as possible to avoid unnecessary and sometimes even incorrect computations.