The Morning after Halloween
Time Limit: 12000MS 64bit IO Format: %lld & %llu
直接搜索时间过不了。
可以先把底图抽出来,这样的话就不用O(maxn*maxn*5)来判断是否可以转移了。
另外,用双向BFS可以减少一半深度的搜索,meet in the middle,另外用hash加速进队出队。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
const int INF=0x3f3f3f3f;
const int maxn = 16*16;
const int dx[5] = { 0,-1,1,0,