poj1741，POJ3278

2023-11-18 阅读 23 评论 0

摘要：　　之前用數組存的每一個位置的步數情況，開的數組大小是100010，過了，后來想改成結構體寫，結構體只用再定義一個標記數組，我標記數組也開的100010，然后就RE了，開成200000就過了　　完整代碼 poj1741、　　 #include <io

　　之前用數組存的每一個位置的步數情況，開的數組大小是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;
}