poj 2965 解题报告－－－【附注】memset()对oj时间的影响

将3个memset注释掉后，发现时间节省了好多呀！哈哈

接下来，我们讨论了：
到底是for快，还是memset快
结果呵呵，memset比for要快好多呢，看来，如果以后初始化，还是选择memset吧！

Source Code

Problem: 2965		User: omycle
Memory: 1524K		Time: 485MS
Language: C++		Result: Accepted

• Source Code
  

  #include <iostream>
  using namespace std;
  #define SIZE 0xFFFF
  bool flag[SIZE];//非顺序存储
  int duilie[SIZE+1];//队列
  int step[SIZE+1];//存储有多少步
  int trace[SIZE+1];//存储前一个结点的index
  typedef struct
  {
  int i;
  int j;
  }Loc;
  Loc ij[SIZE+1];//存储ij的数值
  int b[17];
  int tou=0;//指示头部 
  int wei=0;//指示尾部 
  void Init()
  {
  memset(flag,false,SIZE*sizeof(bool));
  // memset(duilie,0,(SIZE+1)*sizeof(int));
  // memset(step,0,(SIZE+1)*sizeof(int));
  // memset(trace,0,(SIZE+1)*sizeof(int));
  for(int i=0;i<SIZE;i++)
  {
    ij[i].i=0;
    ij[i].j=0;
  }
  }
  void b_site()
  {//找出b[]的数值 
  for(int i=1;i<=16;i++)
  {
    b[i]=1;
    b[i]<<=(i-1);
  }
  }
  //读取其数值 
  void read()
  {
  char s[5];
   s[4]='\0';
  for(int i=1;i<=4;i++)
  {
  scanf("%s",s);
  for(int j=0;j<=3;j++)
  {
     duilie[0]<<=1;
  if(s[j]=='+')
     duilie[0]+=1;
  }
  }
  }
  //
  void Dfs()
  {
   tou=0;
  //5 个数组呢 
   flag[duilie[tou]]=true;
   step[tou]=0;
   ij[0].i=0;
   ij[0].j=0;
   trace[0]=0;
   wei=1;
  while(wei>tou)
  {
  int temp=duilie[tou];
  for(int i=1;i<=16;i++)
  {
     temp=duilie[tou];
  if(i==1||i==5||i==9||i==13)
  {
      temp^=b[1];
      temp^=b[5];
      temp^=b[9];
      temp^=b[13];
      temp^=b[i+1];
      temp^=b[i+2];
      temp^=b[i+3];
  }
  else if(i==2||i==6||i==10||i==14)
  {
      temp^=b[2];
      temp^=b[6];
      temp^=b[10];
      temp^=b[14];
      temp^=b[i-1];
      temp^=b[i+1];
      temp^=b[i+2];
  }
  else if(i==3||i==7||i==11||i==15)
  {
      temp^=b[3];
      temp^=b[7];
      temp^=b[11];
      temp^=b[15];
      temp^=b[i-2];
      temp^=b[i+1];
      temp^=b[i-1];
  }
  else if(i==4||i==8||i==12||i==16)
  {
      temp^=b[4];
      temp^=b[8];
      temp^=b[12];
      temp^=b[16];
      temp^=b[i-1];
      temp^=b[i-2];
      temp^=b[i-3];
  }
  if(!flag[temp])
  {
      flag[temp]=true;
      duilie[wei]=temp;
      step[wei]=step[tou]+1;
      trace[wei]=tou;//存储索引值，一定要记着
  //下面把tou分割一下，放到ij数组里面，哈哈
  switch(i)
  {
  case 1:
       ij[wei].i=4;
       ij[wei].j=4;
  break;
  case 2:
       ij[wei].i=4;
       ij[wei].j=3;
  break;
  case 3:
       ij[wei].i=4;
       ij[wei].j=2;
  break;
  case 4:
       ij[wei].i=4;
       ij[wei].j=1;
  break;
  case 5:
       ij[wei].i=3;
       ij[wei].j=4;
  break;
  case 6:
       ij[wei].i=3;
       ij[wei].j=3;
  break;
  case 7:
       ij[wei].i=3;
       ij[wei].j=2;
  break;
  case 8:
       ij[wei].i=3;
       ij[wei].j=1;
  break;
  case 9:
       ij[wei].i=2;
       ij[wei].j=4;
  break;
  case 10:
       ij[wei].i=2;
       ij[wei].j=3;
  break;
  case 11:
       ij[wei].i=2;
       ij[wei].j=2;
  break;
  case 12:
       ij[wei].i=2;
       ij[wei].j=1;
  break;
  case 13:
       ij[wei].i=1;
       ij[wei].j=4;
  break;
  case 14:
       ij[wei].i=1;
       ij[wei].j=3;
  break;
  case 15:
       ij[wei].i=1;
       ij[wei].j=2;
  break;
  case 16:
       ij[wei].i=1;
       ij[wei].j=1;
  break;
  }
  if(duilie[wei]==0)
  {
  printf("%d\n",step[wei]);//输出步数
  int i_temp=wei;
  while(wei>0)
  {
  printf("%d %d\n",ij[wei].i,ij[wei].j);
        wei=trace[wei];
  }
  return ;
  }
      wei++;
  }
  }
    tou++;
  }
  printf("Impassible\n");
  }
  int main()
  {
  Init();
  b_site();
  read();
  Dfs();
  // system("pause");
  return 0;
  }