HDOJ 1195 Open the Lock (双向BFS)(二)
back_vis[tmp.password];
if(vis.find(tmp.password)==vis.end())
{
tmp.cnt++;
q.push(tmp);
vis[tmp.password]=tmp.cnt;
}
}
for(int i=0;i<3;i++)
{
tmp=now;
swap(tmp.password[i],tmp.password[i+1]);
if(back_vis.find(tmp.password)!=back_vis.end())//判断是否在反向队列中找到
return tmp.cnt+1+back_vis[tmp.password];
if(vis.find(tmp.password)==vis.end())
{
tmp.cnt++;
q.push(tmp);
vis[tmp.password]=tmp.cnt;
}
}
}
int ret=back_bfs(now.cnt);
if(ret!=-1)
return ret;
}
}
int main()
{
int t;
while(cin>>t)
{
while(t--)
{
cin>>beg;
cin>>end;
vis.clear();//清空map
back_vis.clear();//清空map
while(!back_q.empty())
back_q.pop();//清空反向BFS的队列
now.password=end;
now.cnt=0;
back_q.push(now);
back_vis[end]=0;//将反向BFS的起始点入队列标记
int ret=bfs();
cout<
}
}
return 0;
}