为什么这样会超时?跪求大神

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
using namespace std;

typedef int stade[9];
stade start;
stade goal={0};
struct node
{
  stade x;
  vector<int> v;
};
stade l;
bool s[4][4][4][4][4][4][4][4][4];
queue<node> q;
int da[9][9] = { 
    {0, 1, 3, 4, -1 },
    {0, 1, 2, -1 }, 
    {1, 2, 4, 5, -1 },
    {0, 3, 6, -1 },
    {1,3,4,5,7,-1},
    {2,5,8,-1},
    {3,4,6,7,-1},
    {6,7,8,-1},
    {4,5,7,8,-1}
};

void change(node p,int x)
{
  memcpy(&l,&p.x,sizeof(p.x));
  for(int i=0;da[x][i]!=-1;i++)
  {
    l[da[x][i]]++;
    l[da[x][i]]%=4;
  }
}

bool check(stade po)
{
  if(s[po[0]][po[1]][po[2]][po[3]][po[4]][po[5]]
        [po[6]][po[7]][po[8]]==0)
    return 1;
  else 
    return 0;
}

void check1(stade po)
{
  s[po[0]][po[1]][po[2]][po[3]][po[4]][po[5]]
        [po[6]][po[7]][po[8]]=1;
}

void bfs()
{
  node a;
  memcpy(&a.x,&start,sizeof(start));
  a.v.clear();
  q.push(a);
  check1(a.x);
  while(!q.empty())
  {
    node p=q.front();
    if(memcmp(p.x,goal,sizeof(goal))==0)
    {
      for(int i=0;i<p.v.size();i++)
        cout<<p.v[i]+1<<" ";
        return;
    }
    for(int i=0;i<=8;i++)
    {
      change(p,i);
      if(check(l))
      {
        node newq;
        memcpy(&newq.x,&l,sizeof(l));
        newq.v=p.v;
        newq.v.push_back(i);
        q.push(newq);
        check1(l);
      }
    }
    q.pop();
  }
}

int main()
{
  for(int i=0;i<=8;i++)
    cin>>start[i];
  bfs();
  return 0;
}

1 条评论

  • @ 2016-08-16 23:29:55

    只会Pascal 表示一只标准P党。。。[]file:///C:/Users/mrl/Pictures/0[V%7B497]DCWC@(LU_$MAD1L.gif

  • 1

信息

ID
1016
难度
5
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
4361
已通过
1459
通过率
33%
被复制
1
上传者