概述
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1043
这道题很尴尬的是VC里跑的是错的。但是OJ上是A的。
VC中strcpy后让我的赋值语句错了????半天不知道为什么。最后绝望的随便扔了下OJ。A了??
然后我直接给strcpy换成了for循环赋值。MMP
#include<bits/stdc++.h>
#define PI 3.1415926
#define INF 1e18
#define inf 1e9
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std ;
typedef long long ll;
typedef unsigned long long ull;
const int _max=1e6+100;
struct node{
int x,y;
int cnt;
char num[9];
};
char path[_max];
bool vis[_max];
int pre[_max];
int fac[10];
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
queue<struct node> que;
int contour(char *s){
int sum = 0,cnt;
for(int i = 0 ; i < 8 ; i++){
cnt = 0;
for(int j = i+1 ; j < 9 ; j++) if(s[i]>s[j]) cnt++;
sum += cnt*fac[9-i-1];
}
return sum+1;
}
void bfs(){
while(!que.empty()) que.pop();
memset(vis,false,sizeof(vis));
node p,q;
for(int i = 0 ; i < 8 ; i++) p.num[i] = '0'+i+1;
p.x=2;
p.y=2;
p.num[8]='0';
p.cnt = contour(p.num);
vis[p.cnt] = true;
path[p.cnt] = -1;
que.push(p);
while(!que.empty()){
p = que.front();
que.pop();
for(int i = 0 ; i < 4 ; i++){
q.x=p.x+dx[i];
q.y=p.y+dy[i];
if(q.x<0 || q.y<0 || q.x>2 || q.y>2) continue;
int pos = q.x*3+q.y;
int p_pos = p.x*3+p.y;
for(int i = 0 ; i <= 8 ; i++)
q.num[i] = p.num[i];
swap(q.num[pos],q.num[p_pos]);
q.cnt = contour(q.num);
if(!vis[q.cnt]){
vis[q.cnt] = true;
pre[q.cnt] = p.cnt;
switch(i){
case 0:path[q.cnt] = 'l';break;
case 1:path[q.cnt] = 'r';break;
case 2:path[q.cnt] = 'd';break;
default:path[q.cnt] = 'u';
}
que.push(q);
}
}
}
return ;
}
char str[100];
char cc[10];
int tot;
void Print(int f){
int i = f;
while(path[i]!=-1){
printf("%c",path[i]);
i = pre[i];
}
printf("n");
return ;
}
int main(){
fac[0]=1;
for(int i = 1 ; i <= 8 ; i++)
fac[i] = fac[i-1]*i;
bfs();
while(gets(str)!=NULL){
int len = strlen(str);
tot = 0;
for(int i = 0 ; i < len ; i++){
if(str[i] == 'x') cc[tot++]='0';
else if (str[i]>='1' && str[i]<='8') cc[tot++] = str[i];
}
cc[tot] = '