之前用數組存的每一個位置的步數情況,開的數組大小是100010,過了,后來想改成結構體寫,結構體只用再定義一個標記數組,我標記數組也開的100010,然后就RE了,開成200000就過了
完整代碼
poj1741、
#include <iostream> #include <cstring> #include <queue> using namespace std; int k,vis[200000]; int u[3]={1,2,3};struct node {int p,s;node(int a,int b){p=a;s=b; } };void bfs(int n) {queue<node> q;q.push(node(n,0));while(!q.empty()){node t=q.front();q.pop();if(t.p==k){cout<<t.s<<endl;return ;}for(int i=0;i<3;i++){int tx=t.p;if(u[i]==1)//左移 {if(!vis[tx-1] && tx-1>=0 && tx-1<=100000){vis[tx-1]=1;q.push(node(tx-1,t.s+1));}}else if(u[i]==2)//右移 {if(!vis[tx+1] && tx+1>=0 && tx+1<=100000){vis[tx+1]=1;q.push(node(tx+1,t.s+1));}}else if(u[i]==3)//乘2 {if(!vis[tx*2] && tx*2>=0 && tx*2<=100000){vis[tx*2]=1;q.push(node(tx*2,t.s+1));}} } } }int main() {int n;cin>>n>>k;vis[n]=1;bfs(n);return 0; }
?