| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
开数组MLE,用map就T,我擦,我用hash 219ms过的,我擦擦擦,吐血了#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <vector>
using namespace std;
int a[3][3],b[3][3],c[3][3];
const int N=42374117;
const int H=1e7+7;
int beg,vis[N];
int box[H],kk;
struct node
{
int org,vis,next;
}e[H];
int mx[5]={0,-1,0,1,0};
int my[5]={0,0,1,0,-1};
int map_num()
{
int ans=0,p=1;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(i||j)
{
ans+=p*a[i][j];
p*=9;
}
return ans;
}
queue<int>q;
int num_map(int now,int &x,int &y)
{
bool v[10];
memset(v,0,sizeof(v));
for(int i=1;i<9;i++)
{
if(now%9==8)
{
x=i/3;
y=i%3;
}
v[now%9]=1;
a[i/3][i%3]=now%9;
now/=9;
}
for(int i=0;i<9;i++)
if(!v[i])
{
a[0][0]=i;
if(i==8)
{
x=0;
y=0;
}
}
}
bool in(int x,int y)
{
if(x<0||y<0||x>2||y>2) return 0;
return 1;
}
int find(int num)
{
int af=num%H;
for(int i=box[af];~i;i=e[i].next)
if(e[i].org==num) return e[i].vis;
return 0;
}
void add(int s,int num,int vis)
{
e[kk].org=num;e[kk].vis=vis,e[kk].next=box[s];
box[s]=kk++;
}
void hash_add(int num,int vis)
{
add(num%H,num,vis);
}
void pre()
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++) a[i][j]=i*3+j;
q.push(beg=map_num());
memset(box,-1,sizeof(box));
int cat=0;
while(!q.empty())
{
int now=q.front();q.pop();
int x,y;
num_map(now,x,y);
for(int i=1;i<=4;i++)
{
int nx=x+mx[i];
int ny=y+my[i];
if(!in(nx,ny)) continue;
swap(a[x][y],a[nx][ny]);
int nextNum=map_num();
swap(a[x][y],a[nx][ny]);
if(find(nextNum)) continue;
else
{
hash_add(nextNum,i);
q.push(nextNum);
++cat;
}
}
}
}
string s;
void dfs(int x,int y,int level)
{
int key=find(map_num());
int nx=x-mx[key];
int ny=y-my[key];
if(map_num()==beg) return;
char ch;
switch(key)
{
case 1:ch='d';break;
case 2:ch='l';break;
case 3:ch='u';break;
case 4:ch='r';break;
}
printf("%c",ch);
swap(a[x][y],a[nx][ny]);
dfs(nx,ny,level+1);
}
void init()
{
int x,y;
for(int i=0;i<9;i++)
{
char s[2];scanf("%s",s);
if(s[0]=='x') a[i/3][i%3]=8;
else a[i/3][i%3]=s[0]-'1';
if(a[i/3][i%3]==8)
{
x=i/3;
y=i%3;
}
}
int nowNum=map_num();
if(find(nowNum))
{
dfs(x,y,1);
puts("");
}else puts("unsolvable");
}
int main()
{
//freopen("in.txt","r",stdin);
pre();
init();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator