[cdoj1380] Xiper的奇妙历险(3) (八数码问题 bfs + 预处理)

快要NOIP 2016 了,现在已经停课集训了。计划用10天来复习以前学习过的所有内容。首先就是搜索。

八数码是一道很经典的搜索题,普通的bfs就可求出。为了优化效率,我曾经用过康托展开来优化空间,甚至还用过A*来优化时间。不过这道题懒得写了,就一个普普通通的bfs,再加上一个stl 的map就水过了。

首先题目要求有多达10000组数据,依次搜索肯定是不行的,我试过用A*来写,第2组数据就会T掉,所以我们考虑用一个预处理。从末尾状态搜索所有可行的状态,并用一个map来存储答案。然后就很好写了。

不过最智障的是,我用getchar读入数据,手测数据都对,交上去wa了无数次,改了快一晚上才发现是读入挂了。辣鸡getchar[cdoj1380] Xiper的奇妙历险(3) (八数码问题 bfs + 预处理)

 #include <iostream>
#include <map>
#include <queue>
#include <cstdio>
using namespace std;
typedef pair <int ,int> pis;
#define OK(a,b) (a < 3 && a >= 0 && b < 3 && b >= 0) int t;
map <long long, int > MAP;
queue <pis > q; int mx[] = {,-,,};
int my[] = {,,-,}; inline int E(int x){return x== ? : * E(x-);} inline void bfs(){
int u = ;
int p;
MAP[u] = ;
q.push(make_pair(u,));
while(!q.empty()){
u = q.front().first; p = q.front().second;q.pop();
int x = p / , y = p % ;
for(int i = ;i < ;i++){
int nx = x + mx[i];
int ny = y + my[i];
if(OK(nx,ny)){
int nu = u;
int xx = (nu % E(-(nx * + ny))) / E(-(nx * + ny));
nu -= xx * E(-(nx * + ny));
nu += xx * E(-p);
if(!MAP[nu]){
MAP[nu] = MAP[u] + ;
q.push(make_pair(nu,nx*+ny));
}
}
}
} } int main(){
bfs(); scanf("%d",&t);
char s[];
while(t--){
int m = ;
for(int i = ;i < ;i++){
scanf("%s",s);
m = m * + (s[] == 'x' ? : (s[] - ''));
}
printf("%d\n",MAP[m] - );
} return ;
}
上一篇:[Leetcode Week8]Triangle


下一篇:HTC学习笔记