POJ 3278 Catch That Cow（简单BFS + 动态方向的设置）

梦里梦外; 2024-02-17 19:06 180阅读 0赞

RE了三次，原因是数组越界，解决方法是1、把数组开大些（边界判断条件（1e5）的两倍以上） 2、把数组判断d[v]放在边界判断之后 。 AC代码如下:

  1. #include<cstdio>
  2. #include<queue>
  3. #include<cstring>
  4. using namespace std;
  5. const int maxn=1e5+10;
  6. int d[maxn];
  7. int N,K;
  8. int dir[]={-1,1,N};
  9. void bfs(){
  10.     memset(d,0,sizeof(d));
  11.     queue<int>q;
  12.     q.push(N);
  13.     while(!q.empty()){
  14.         int u=q.front();
  15.         q.pop();
  16.         N=u;        //更新N
  17.         if(u==K){
  18.             printf("%d\n",d[u]);
  19.             return ;
  20.         }
  21.         for(int i=0;i<3;i++){
  22.             int v;
  23.             if(i<2)v=u+dir[i];
  24.             else v=2*N;
  25.             if(v>=0&&v<=1e5 && !d[v]){
  26.                 q.push(v);
  27.                 d[v]=d[u]+1; 
  28.             }
  29.         }
  30.     }
  31. }
  32. int main(){
  33.     while(scanf("%d%d",&N,&K)==2){
  34.         bfs();
  35.     }
  36.     return 0;
  37. }

发表评论

表情：
评论列表 （有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读