完美超时....

暴搜没有剪枝 #滑稽
开始怀疑STL效率了
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#define ADD(x) ((((x) + 1) > 3) ? (0) : ((x) + 1))
using namespace std;

int thing[9][10] = {
{4, 0, 1, 3, 4 },
{3, 0, 1, 2 },
{4, 1, 2, 4, 5 },
{3, 0, 3, 6 },
{5, 1, 3, 4, 5, 7},
{3, 2, 5, 8 },
{4, 3, 4, 6, 7 },
{3, 6, 7, 8 },
{4, 4, 5, 7, 8 },
};
queue<vector<int> > road, doth;
set <vector<int> > used;

int ok(vector<int> &x)
{
int i;

for(i = 0;i < 9;i ++)
if(x.at(i))
return 0;
return 1;
}

void print(int &x)
{
cout << x << ' ';

return;
}

void bfs(vector<int> &sta)
{
int i, j;
vector<int> tv, td;

tv.clear();
road.push (sta);
doth.push (tv );
used.insert(sta);

while(!road.empty())
{
for(i = 0;i < 9;i ++)
{
tv = road.front();
td = doth.front();
for(j = 1, td.push_back(i + 1);j <= thing[i][0];j ++)
tv.at(thing[i][j]) = ADD(tv.at(thing[i][j]));
if(used.count(tv))
continue;

if(ok(tv))
{
for_each(td.begin(), td.end(), print);
cout << endl;

return;
}
road.push (tv);
doth.push (td);
used.insert(tv);
}
road.pop();
doth.pop();
}

return;
}

int main()
{
vector<int> sta;
int i, j;

for(i = 0;i < 9;i ++)
{
cin >> j;
sta.push_back(j);
}
bfs(sta);

return 0;
}
```

2 条评论

  • 1

信息

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