Queue FIFO search speed up through the change of visited array? As I was preparing for the CCC this year, I am quite confused as to why a certain code modification was able to speed up my code for CCC Seniors Problem 2.
Here was the C++ source code for my first attempt, which scored 13/15 in the cccgrader website as well as the DMOJ online judging website.
#include &lt;bits/stdc++.h&gt;
using namespace std;
typedef vector&lt;int&gt; vint;
typedef pair&lt;int,int&gt; pii;
vector&lt;pii&gt; vpairs[1000001];
vector&lt;vector&lt;bool&gt;&gt; vis;
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int A,B;
    cin&gt;&gt;A&gt;&gt;B;
    for(int i=0;i&lt;A;i++)
    {
        vector&lt;bool&gt; newvecbool;
        for(int j=0;j&lt;B;j++)
        {
            newvecbool.push_back(false);
            int k;
            cin&gt;&gt;k;
            vpairs[k].push_back(pii(i,j));
        }
        vis.push_back(newvecbool);
    }
    queue&lt;pii&gt; queue;
    queue.push(pii(A,B));
    while(!queue.empty())
    {
        pii curpair = queue.front();
        queue.pop();
        if(curpair.first==1 &amp;&amp; curpair.second==1){
            cout&lt;&lt;&quot;yes&quot;;
            return 0;
        }
        vis[curpair.first-1][curpair.second-1] = true;
        int value = curpair.first*curpair.second;
       // cout&lt;&lt;curpair.first&lt;&lt;' '&lt;&lt;curpair.second&lt;&lt;endl;
        for(int i=0; i&lt;vpairs[value].size();i++)
        {
            pii pair = vpairs[value][i];
            if(!vis[pair.first][pair.second]){
                //vis[pair.first][pair.second] = true;
                queue.push(pii(pair.first+1,pair.second+1));
            }
        }
    }
    cout&lt;&lt;&quot;no&quot;;
}

Here, on the other hand, was my second attempt, being much faster in time and scoring 15/15 on both the cccgrader and the DMOJ judging website.
#include &lt;bits/stdc++.h&gt;
using namespace std;
typedef vector&lt;int&gt; vint;
typedef pair&lt;int,int&gt; pii;
vector&lt;pii&gt; vpairs[1000001];
vector&lt;vector&lt;bool&gt;&gt; vis;
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int A,B;
    cin&gt;&gt;A&gt;&gt;B;
    for(int i=0;i&lt;A;i++)
    {
        vector&lt;bool&gt; newvecbool;
        for(int j=0;j&lt;B;j++)
        {
            newvecbool.push_back(false);
            int k;
            cin&gt;&gt;k;
            vpairs[k].push_back(pii(i,j));
        }
        vis.push_back(newvecbool);
    }
    queue&lt;pii&gt; queue;
    queue.push(pii(A,B));
    while(!queue.empty())
    {
        pii curpair = queue.front();
        queue.pop();
        if(curpair.first==1 &amp;&amp; curpair.second==1){
            cout&lt;&lt;&quot;yes&quot;;
            return 0;
        }
        //vis[curpair.first-1][curpair.second-1] = true;
        int value = curpair.first*curpair.second;
       // cout&lt;&lt;curpair.first&lt;&lt;' '&lt;&lt;curpair.second&lt;&lt;endl;
        for(int i=0; i&lt;vpairs[value].size();i++)
        {
            pii pair = vpairs[value][i];
            if(!vis[pair.first][pair.second]){
                vis[pair.first][pair.second] = true;
                queue.push(pii(pair.first+1,pair.second+1));
            }
        }
    }
    cout&lt;&lt;&quot;no&quot;;
}

As you may have noticed, the only difference between the two source codes is the position in which the vis vector, a vector used to store the pairs of integers of visited coordinates,  is set to true. after visit of a coordinate point. One is right after the if statement, whilst one is in the while loop. I'm not quite sure what led to the speed increase.
Any help will be greatly appreciated.
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.