评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 504 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 504 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 500 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 504 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 504 KiB, score = 10
Accepted, time = 15 ms, mem = 508 KiB, score = 100

本题贪心即可
题目等价于移动‘1’到目标图案中1的位置
首先求出地图上各点的距离
首先找出不需要动的点，标记
然后访问每一个需要移动的点
依次找到移动最短的路途所能，移动到哪一个点，
做标记，更新dist

#include <cstdio>
#include <algorithm>

struct dest{
    int n,dist;
}temp[9];

bool cmp(dest a,dest b){
    return a.dist<b.dist;
}

int abs(int x){
    if(x>0)
        return x;
    else
        return -1*x;
}

int getdist(int a,int b){
    int xa,xb,ya,yb,dx,dy;
    xa=(a-1)/4 +1,xb=(b-1)/4 +1;
    ya=a-4*(xa-1),yb=b-4*(xb-1);
    dx=abs(xa-xb),dy=abs(ya-yb);
    return dx+dy;
}

int main(){
    //freopen("in.txt","r",stdin);
    int map[17][17]={0};
    int st[9],end[9],n=0;
    for(int i=1;i<=16;i++)
    for(int j=1;j<=16;j++)
        map[i][j]=getdist(i,j);
        
    for(int i=1;i<=16;i++){
        int q;
        scanf("%1d",&q);
        if(q==1)
            st[++n]=i;
    }
    n=0;
    for(int i=1;i<=16;i++){
        int q;
        scanf("%1d",&q);
        if(q==1)
            end[++n]=i;
    }   
    
    int distance=0,vis[17]={0},add[9]={0};
    
    for(int i=1;i<=8;i++){
        for(int z=1;z<=8;z++){
            temp[z].n=z;
            temp[z].dist=map[st[i]][end[z]];
        }
        std::sort(temp+1,temp+1+n,cmp);
        if(temp[1].dist==0)
            vis[temp[1].n]=1,add[i]=1;
    }
    
    
    for(int i=1;i<=8;i++){
        if(add[i])
            continue;
        for(int z=1;z<=8;z++){
            temp[z].n=z;
            temp[z].dist=map[st[i]][end[z]];
        }
        std::sort(temp+1,temp+1+n,cmp);
        int p=0,flag;
        do{
            p++;
            flag=0;
            if(vis[temp[p].n]==0){
                vis[temp[p].n]=1;
                distance+=temp[p].dist;
            }   
            else
                flag=1;
        }while(flag);
    }
    printf("%d",distance);
        return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 1128 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1128 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1124 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1124 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1128 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1124 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1128 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1128 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1128 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1128 KiB, score = 10
Accepted, time = 15 ms, mem = 1128 KiB, score = 100
题解
http://www.cnblogs.com/Coolxxx/p/5308223.html（偷偷赚个访问量）
或者 http://blog.csdn.net/u010568270/article/details/50957967

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 508 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 500 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 504 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 504 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 504 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 504 KiB, score = 10

测试数据 #6: TimeLimitExceeded, time = 1015 ms, mem = 496 KiB, score = 0

测试数据 #7: TimeLimitExceeded, time = 1203 ms, mem = 496 KiB, score = 0

测试数据 #8: TimeLimitExceeded, time = 1203 ms, mem = 492 KiB, score = 0

测试数据 #9: TimeLimitExceeded, time = 1203 ms, mem = 496 KiB, score = 0

TimeLimitExceeded, time = 4639 ms, mem = 508 KiB, score = 60

居然是bfs+位运算，小生打了ida*超时了。。。
顺便说一句，输出结果只需输出一行答案就行！别多输出一行空行！小生就是多输出了一行空行导致wa了两次！（最重要的是那两次居然还得了10分= =）

又一道位运算BFS, 秒杀

//vijos 1206
#include <stdio.h>
#include <stdlib.h>

#define STATUS 0
#define STEP 1

int queue[100000][2];
int answer[1<<16];
int head = 0, tail = 0;

void addToQueue(int status, int step){
if(answer[status] < 0){
queue[tail][STATUS] = status;
queue[tail][STEP] = step;
answer[status] = step;
tail++;
}
}
int get(int status, int index){
return 1&(status>>index);
}
void set(int *status, int index, int value){
*status &= ~(1<<index);
*status |= (value&1)<<index;
}
int main(){
char line[10];
int i, k, this, adjacent, step, status, target;

for(i=0; i<(1<<16); i++)
answer[i] = -1;

status = 0;
for(i=0; i<4; i++){
scanf("%s", line);
for(k=0; k<4; k++){
status <<= 1;
status |= line[k]-'0';
}
}
addToQueue(status, 0);

target = 0;
for(i=0; i<4; i++){
scanf("%s", line);
for(k=0; k<4; k++){
target <<= 1;
target |= line[k]-'0';
}
}

while(head < tail){
status = queue[head][STATUS];
step = queue[head][STEP];
if(status == target)
break;
for(i=0; i<16; i++){
this = get(status, i);
if(i%4 != 0){
adjacent = get(status, i-1);
k = status;
set(&k, i, adjacent);
set(&k, i-1, this);
addToQueue(k, step+1);
}
if(i%4 != 3){
adjacent = get(status, i+1);
k = status;
set(&k, i, adjacent);
set(&k, i+1, this);
addToQueue(k, step+1);
}
if(i/4 != 0){
adjacent = get(status, i-4);
k = status;
set(&k, i, adjacent);
set(&k, i-4, this);
addToQueue(k, step+1);
}
if(i/4 != 3){
adjacent = get(status, i+4);
k = status;
set(&k, i, adjacent);
set(&k, i+4, this);
addToQueue(k, step+1);
}
}
head++;
}
printf("%d\n", answer[target]);

return 0;
}

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

const int dr[] ={1, 0, -1, 0};
const int dc[] ={0, 1, 0, -1};
const int INF = 100000000;

int s, t, a[5][5], d[1000000], vis[1000000];
char buf[6];

struct P{
int u[5][5], c;
};
int bfs(){
queue<P>q;
for(int i = 0; i < 1000000; i++)d[i] = INF;
d[s] = 0;
P p;
memcpy(&p.u, &a, sizeof(a)); p.c = s;
q.push(p);

while(!q.empty()){

P p = q.front(); q.pop();

if(p.c == t)break;

for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
for(int k = 0; k < 4; k++){
int x = i + dr[k], y = j + dc[k];
if(x >= 0&&x < 4&&y >= 0&&y < 4&&p.u[i][j] != p.u[x][y]){

P h;
memcpy(&h.u, &p.u, sizeof(p.u));
swap(h.u[i][j], h.u[x][y]);

int l = 0, c = 0;
for(int n = 0; n < 4; n++){
for(int m = 0; m < 4; m++){
if(h.u[n][m])c += (1 << l); l++;
}
}

if(!vis[c]&&d[c] >= d[p.c]+1){
vis[c] = 1;
d[c] = d[p.c]+1; h.c = c;
q.push(h);
}
}
}
}
return d[t];
}

int main()
{
int c = 0;
for(int i = 0; i < 4; i++){
scanf("%s", buf);
for(int j = 0; j < 4; j++){
a[i][j] = buf[j]-'0';
if(a[i][j])s += (1<<c);
c++;
}
}

int x; c = 0;
for(int i = 0; i < 4; i++){
scanf("%s", buf);
for(int j = 0; j < 4; j++){
x = buf[j] - '0';
if(x)t += (1<<c);
c++;
}
}
printf("%d", bfs());

return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 79064 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 79064 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 79072 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 79064 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 79064 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 79064 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 79072 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 79068 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 79072 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 79068 KiB, score = 10
Accepted, time = 30 ms, mem = 79072 KiB, score = 100
BFS+位运算

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=70000;
struct p{
int g[5][5];
int s;
};
p que[maxn],a,b,t;
bool vis[maxn],ok;
int head,tail;
int getnum(p x){
int i,j,res=0;
for(i=1;i<=4;++i){
for(j=1;j<=4;++j){
res<<=1;
res+=x.g[i][j];
}
}
return res;
}
int main(){
int tar,i,j,l;
for(i=1;i<=4;++i)
for(j=1;j<=4;++j)
scanf("%1d",&a.g[i][j]);
for(i=1;i<=4;++i)
for(j=1;j<=4;++j)
scanf("%1d",&b.g[i][j]);
a.s=0;
que[tail++]=a;
vis[getnum(a)]=1;
tar=getnum(b);
if(vis[tar]){
printf("0\n");
return 0;
}
for(;;){
t=que[head];
t.s++;
for(i=4;i>0;--i){
for(j=4;j>0;--j){
if(i<4){
swap(t.g[i][j],t.g[i+1][j]);
l=getnum(t);
if(tar==l){
printf("%d\n",t.s);
return 0;
}
if(!vis[l]){
vis[l]=1;
que[tail++]=t;
}
swap(t.g[i][j],t.g[i+1][j]);
}
if(j<4){
swap(t.g[i][j],t.g[i][j+1]);
l=getnum(t);
if(tar==l){
printf("%d\n",t.s);
return 0;
}
if(!vis[l]){
vis[l]=1;
que[tail++]=t;
}
swap(t.g[i][j],t.g[i][j+1]);
}
}
}
head++;
}
}
未能秒杀╮(╯_╰)╭

program bz1054;
const
dx:array[1..4]of longint=(0,1,0,-1);
dy:array[1..4]of longint=(1,0,-1,0);
var
yix,yiy,wei:array[0..100]of longint;
gs,i,n,j,oi,zt,mudi,t,w,mbzt,x,y,xx,yy:longint;
o:char;
a:array[0..100,0..100]of longint;
dis,d:array[0..1000000]of longint;
bb:array[0..1000000]of boolean;
procedure be;
begin
assign(input,'1054.in');
assign(output,'1054.out');
reset(input);
rewrite(output);
end;
procedure en;
begin
close(input);
close(output);
end;
function biaohao(x,y:longint):longint;
begin
biaohao:=17-(x-1)*4-y;
end;
function panduan(zt,j:longint):longint; {1,1为最高位；标号16， 4,4 为最低位}
var
bh1,bh2:longint;
begin
bh1:=biaohao(x,y);
bh2:=biaohao(xx,yy);
zt:=zt-wei[bh1]+wei[bh2];
panduan:=zt;
end;

begin
//be;

fillchar(dis,sizeof(dis),127);
wei[1]:=1;
for i:=2 to 18 do
wei[i]:=wei[i-1]<<1;
for i:=1 to 4 do
begin
for j:=1 to 4 do
begin
read(o);
oi:=ord(o)-48;
//xx:=xx+1;
zt:=(zt<<1)+oi;
end;
readln;
end;
dis[zt]:=0;
readln;
//xx:=0

for i:=1 to 4 do
begin
for j:=1 to 4 do
begin
read(o);
oi:=ord(o)-48;
mudi:=(mudi<<1)+oi;
end;
readln;
end;
t:=1;
w:=1;
d[t]:=zt;
fillchar(bb,sizeof(bb),true);
bb[zt]:=false;
repeat
zt:=d[t];
gs:=0;
for i:=4 downto 1 do
for j:=4 downto 1 do
begin
a[i,j]:=zt and 1;
if a[i,j]=1 then
begin
gs:=gs+1;
yix[gs]:=i;
yiy[gs]:=j;
end;
zt:=zt>>1;
end;
zt:=d[t];
for i:=1 to gs do
begin
x:=yix[i]; y:=yiy[i];
for j:=1 to 4 do
begin
xx:=x+dx[j]; yy:=y+dy[j];
if (xx>0)and(xx<=4)and(yy>0)and(yy<=4) then
begin
mbzt:=panduan(zt,j);
if dis[zt]+1<dis[mbzt] then
begin
dis[mbzt]:=dis[zt]+1;
if bb[mbzt] then
begin
bb[mbzt]:=false;
w:=w+1;
d[w]:=mbzt;
end;
end;
end;
end;
end;
bb[zt]:=true;
t:=t+1;
until t>w;
writeln(dis[mudi]);
en;
end.

河南省选2006 做起来就是个spfa

测试数据 #0: Accepted, time = 0 ms, mem = 1848 KiB, score = 10
测试数据 #1: Accepted, time = 7 ms, mem = 1852 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1844 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1852 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1848 KiB, score = 10
测试数据 #5: Accepted, time = 7 ms, mem = 1852 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 1844 KiB, score = 10
测试数据 #7: Accepted, time = 7 ms, mem = 1848 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 1844 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1848 KiB, score = 10
顺便发一下这个