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 <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pii;
vector<pii> vpairs[1000001];
vector<vector<bool>> vis;
int main(void){
ios<IP_ADDRESS>sync_with_stdio(0);cin.tie(0);cout.tie(0);
int A,B;
cin>>A>>B;
for(int i=0;i<A;i++)
{
vector<bool> newvecbool;
for(int j=0;j<B;j++)
{
newvecbool.push_back(false);
int k;
cin>>k;
vpairs[k].push_back(pii(i,j));
}
vis.push_back(newvecbool);
}
queue<pii> queue;
queue.push(pii(A,B));
while(!queue.empty())
{
pii curpair = queue.front();
queue.pop();
if(curpair.first==1 && curpair.second==1){
cout<<"yes";
return 0;
}
vis[curpair.first-1][curpair.second-1] = true;
int value = curpair.first*curpair.second;
// cout<<curpair.first<<' '<<curpair.second<<endl;
for(int i=0; i<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<<"no";
}
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 <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pii;
vector<pii> vpairs[1000001];
vector<vector<bool>> vis;
int main(void){
ios<IP_ADDRESS>sync_with_stdio(0);cin.tie(0);cout.tie(0);
int A,B;
cin>>A>>B;
for(int i=0;i<A;i++)
{
vector<bool> newvecbool;
for(int j=0;j<B;j++)
{
newvecbool.push_back(false);
int k;
cin>>k;
vpairs[k].push_back(pii(i,j));
}
vis.push_back(newvecbool);
}
queue<pii> queue;
queue.push(pii(A,B));
while(!queue.empty())
{
pii curpair = queue.front();
queue.pop();
if(curpair.first==1 && curpair.second==1){
cout<<"yes";
return 0;
}
//vis[curpair.first-1][curpair.second-1] = true;
int value = curpair.first*curpair.second;
// cout<<curpair.first<<' '<<curpair.second<<endl;
for(int i=0; i<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. 268