KM

最小费用最大流..

经典KM,貌似黑书上摘的那道黑白棋吧。。

BFS+hash

就是麻烦了点

广搜+编码

注意:如果要写广搜过程的话,一定要把n大n大的数组开在主程序里,否则堆栈溢出.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

用无敌随机化贪心ac了

可以把题目模型转化为求8个点二分图最大权匹配.

权值就是一个黑格到另一个黑格的距离.

之后可以用p1228的题解中的思路去ac

代码实现十分简单.

经过测试

随机化400次就足以ac

不过建议大家还加多几次随机化次数

Easy!!!!!

和1029一样..........都要编码!!!!!!!

在那里见过～～～

广搜

2进制表示状态

注意先判断初始和目标相同的情况

8个点最大权匹配就可以了.

只要枚举每个点对应的目标,求出路程和,取最小即可

O(8!) 直接DFS不存在时间问题

搜索中间过程可能出现的状态是愚蠢的

BFS+HASH OR DFS+*A剪枝。。。你想晕死我啊

还是O(8!)比较管用

只需要递归 把初始状态的第几个格子和目标状态的第几个格子换就OK了

因为步数就是横坐标差 加 纵坐标差

bfs

2进制表示状态

注意先判断初始和目标相同的情况

4x4循环时对于每个格子只要考虑与右边和下边的对换

且将要交换的两格是相同时不用做下去了

被相同的特殊情况阴了

BFS+HASH OR DFS+*A剪枝

2进制转10进制保存状态...

可是这难度...

搜索题真的好。。

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

typedef int stade[16];
struct node
{
    stade x;
    int step;
};
stade goal,a;
queue<node> q;
set<int> vis;
int f[4]={1,-1,4,-4};

int change(stade o)
{
    int ans=0,u=1;
    for(int i=15;i>=0;i--)
    {
        ans+=o[i]*u;
        u*=2;
    }
    return ans;
}

int main()
{
    int xxxx,p=0;
    for(int i=0;i<4;i++)
    {
        cin>>xxxx;
        a[p++]=xxxx/1000;
        a[p++]=(xxxx/100)%10;
        a[p++]=(xxxx/10)%10;
        a[p++]=xxxx%10;
    }
    p=0;
    for(int i=0;i<4;i++)
    {
        cin>>xxxx;
        goal[p++]=xxxx/1000;
        goal[p++]=(xxxx/100)%10;
        goal[p++]=(xxxx/10)%10;
        goal[p++]=xxxx%10;
    }
    vis.insert(change(a));
    node po;
    memcpy(&po.x,&a,sizeof(a));
    po.step=0;
    q.push(po);
    
    while(!q.empty())
    {
        node r=q.front();
        q.pop();
        if(memcmp(goal,r.x,sizeof(goal))==0)
        {
            cout<<r.step<<endl;
            return 0;
        }
        for(int i=0;i<=15;i++)
            if(r.x[i])
            {for(int j=0;j<4;j++)
                        {
                            if((i==3||i==7||i==11||i==15)&&j==0)    continue;
                            if((i==0||i==4||i==8||i==12)&&j==1)     continue;
                            if((i==12||i==13||i==14||i==15)&&j==2)  continue;
                            if((i==0||i==1||i==2||i==3)&&j==3)      continue;
            
                            if(r.x[i]!=r.x[i+f[j]])
                            {
                                node ll;
                                memcpy(&ll.x,&r.x,sizeof(r.x));
                                swap(ll.x[i],ll.x[i+f[j]]);
                                int i1=change(ll.x);
                                if(!vis.count(i1))
                                {
                                    ll.step=r.step+1;
                                    q.push(ll);
                                    vis.insert(i1);
                                }
                            }
                        }}
    }
    return 0;
}
     

基础宽搜，状压求稳
第二个点输出0 QVQ
```c++
type gdc=record
num,tm:longint;
end;
var
w:array[0..100000] of gdc;
v:array[0..70000] of boolean;
tar,ans,t:longint;
map,map1:array[1..4,1..4] of char;
function pow(x,y:longint):longint;
var
ans,i:longint;
begin
ans:=1;
for i:= 1 to y do
begin
ans:=ans*x;
end;
exit(ans);
end;
function toten(s:string):longint;
var
i,num:longint;
begin
num:=0;
for i:= length(s) downto 1 do
begin
num:=num+(ord(s[i])-48)*pow(2,length(s)-i);
end;
exit(num);
end;
function totwo(num:longint):string;
var
s:string;b:longint;
begin
b:=0;
s:='';
while num<>0 do
begin
b:=num mod 2;
s:=chr(b+48)+s;
num:=num div 2;
end;
exit(s);
end;
procedure readin;
var
i,j:longint; s1,s2:string; ch:char;
begin
s1:='';s2:='';
for i:= 1 to 4 do
begin
for j:= 1 to 4 do
begin
read(ch);
s1:=s1+ch;
end;
readln;
end;
readln;
for i:= 1 to 4 do
begin
for j:= 1 to 4 do
begin
read(ch);
s2:=s2+ch;
end;
readln;
end;
tar:=toten(s2);
w[0].num:=toten(s1);
w[0].tm:=0;
t:=1; // writeln(tar,w[0].num);
for i:= 0 to 70000 do v[i]:=false;
end;

procedure bfs(h:longint);
var
s:string;i,j,k,L,zhi:longint;tmpc:char;
begin
s:=totwo(w[h].num);
if length(s)<16 then for i:= 1 to 16-length(s) do s:='0'+s;

zhi:=0;
for i:= 1 to 4 do
begin
for j:= 1 to 4 do
begin
inc(zhi);
map[i,j]:=s[zhi];
end;
end;

for i:= 1 to 4 do
begin
for j:= 1 to 4 do
begin
if (i>1) and (map[i,j]<>map[i-1,j]) then
begin
map1:=map;
tmpc:=map1[i,j];
map1[i,j]:=map1[i-1,j];
map1[i-1,j]:=tmpc;
s:='';
for k:= 1 to 4 do
begin
for L:= 1 to 4 do
begin
s:=s+map1[k,L];
end;
end;
w[t].num:=toten(s);
w[t].tm:=w[h].tm+1;
if (w[t].num)=tar then begin ans:=w[t].tm;exit; end;
if (v[w[t].num]=false) then begin v[w[t].num]:=true;inc(t); end;
end;
if (j>1) and (map[i,j]<>map[i,j-1]) then
begin
map1:=map;
tmpc:=map1[i,j];
map1[i,j]:=map1[i,j-1];
map1[i,j-1]:=tmpc;
s:='';
for k:= 1 to 4 do
begin
for L:= 1 to 4 do
begin
s:=s+map1[k,L];
end;
end;
w[t].num:=toten(s);
w[t].tm:=w[h].tm+1;
if (w[t].num)=tar then begin ans:=w[t].tm;exit; end;
if (v[w[t].num]=false) then begin v[w[t].num]:=true;inc(t); end;
end;
end;
end;
bfs(h+1);
end;
begin
readin;
if (w[0].num=tar) then writeln(0) else
begin bfs(0);
writeln(ans); end;
end.
```

直接暴力...
pascal
program P1206;
const
p:array[0..15] of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768);
type
arr=array[1..16] of boolean;
ty=record
map:arr;
depth:longint;
end;
var
list:array[1..200000] of ty;
hash:array[0..65536] of boolean;
i,j,t,open,closed:longint;
start,final:arr;
function find(x:arr):boolean;
var
i:longint;
begin
for i:=1 to 16 do if x[i]<>final[i] then exit(false);
exit(true);
end;
function bin(x:arr):longint;
var
i:longint;
begin
bin:=0;
for i:=16 downto 1 do if x[i] then inc(bin,p[16-i]);
end;
procedure dfs(x,y:shortint);
var
t:arr;
k:boolean;
temp:longint;
begin
t:=list[open].map;
k:=t[x];
t[x]:=t[y];
t[y]:=k;
temp:=bin(t);
if find(t) then
begin
writeln(list[open].depth+1);
halt;
end;
if not hash[temp] then
begin
list[closed].map:=t;
list[closed].depth:=list[open].depth+1;
hash[temp]:=true;
inc(closed);
end;
end;
begin
for i:=1 to 4 do
begin
readln(t);
for j:=4 downto 1 do
begin
if t mod 10=1 then start[(i-1)*4+j]:=true
else start[(i-1)*4+j]:=false;
t:=t div 10;
end;
end;
readln;
for i:=1 to 4 do
begin
readln(t);
for j:=4 downto 1 do
begin
if t mod 10=1 then final[(i-1)*4+j]:=true
else final[(i-1)*4+j]:=false;
t:=t div 10;
end;
end;
list[1].map:=start;
list[1].depth:=0;
open:=1;closed:=2;
if find(start) then
begin
writeln(0);
halt;
end;
fillchar(hash,sizeof(hash),false);
hash[bin(start)]:=true;
repeat
dfs(1,2);dfs(2,3);dfs(3,4);dfs(5,6);dfs(6,7);dfs(7,8);dfs(9,10);dfs(10,11);dfs(11,12);dfs(13,14);dfs(14,15);dfs(15,16);
dfs(1,5);dfs(5,9);dfs(9,13);dfs(2,6);dfs(6,10);dfs(10,14);dfs(3,7);dfs(7,11);dfs(11,15);dfs(4,8);dfs(8,12);dfs(12,16);
inc(open);
until open=closed;
end.


wocao,开数组的时候忘了<<的优先级，来了个1<<26的数组

#include<iostream>
        #include<queue>
        #include<algorithm>

        using namespace std;


        const int maxn=(1<<16)+10;
        queue<int> q;
        bool a[5][5],b[5][5];
        int d[maxn],vis[maxn]={0};
        const int dx[]={0,0,1,-1},dy[]={-1,1,0,0};

        int bfs(int start,int finish) {
            q.push(start);
            d[start]=0;
            while (!q.empty()) {

                int u=q.front();    q.pop();
                //cout<<"now u is "<<u<<endl;
                if (u==finish) return d[u];
                bool a[5][5]={0};
                int x=u;
                for (int i=0;i<16;++i) {
                    a[i/4][i%4]=x%2;
                    x/=2;
                }
                /*
                for (int i=0;i<4;++i) {
                    for (int j=0;j<4;++j) cout<<a[i][j]<<' ';
                    cout<<endl;
                }
                */
                for (int i=0;i<4;++i) {
                    for (int j=0;j<4;++j) if (a[i][j]) {
                        //cout<<a[i][j];
                        for (int k=0;k<4;++k) {
                            int nx=i+dx[k],ny=j+dy[k];
                            if (a[nx][ny]||nx<0||nx>3||ny<0||ny>3) continue;
                            swap(a[i][j],a[nx][ny]);
                            int v=0;
                            for (int ii=0;ii<4;++ii) {
                                for (int jj=0;jj<4;++jj) {
                                    v+=a[ii][jj]<<(ii*4+jj);
                                }
                            }
                            if (!vis[v]) {
                                d[v]=d[u]+1;
                                q.push(v);
                                vis[v]=1;
                            }
                            swap(a[i][j],a[nx][ny]);
                        }   
                    //cout<<endl;
                    }
                }
            }
            return -1;
        }

        int main() {
            //freopen("in.txt","r",stdin);
            int start=0,finish=0;
            for (int i=0;i<4;++i) {
                for (int j=0;j<5;++j) {
                    a[i][j]=cin.get()-'0';
                }
            }
            for (int i=0;i<4;++i) {
                for (int j=0;j<4;++j) {
                    start+=a[i][j]<<(i*4+j);
                }
            }
            //cout<<"start is "<<start<<endl;;
            cin.get();
            for (int i=0;i<4;++i) {
                for (int j=0;j<5;++j) {
                    b[i][j]=cin.get()-'0';
                }
            }
            for (int i=0;i<4;++i) {
                for (int j=0;j<4;++j) {
                    finish+=b[i][j]<<(i*4+j);
                }
            }
            //cout<<"finish is "<<finish<<endl;;
            //for (int i=0;i<maxn;++i) d[i]=maxn;

            cout<<bfs(start,finish);

            return 0;
        }

暴力深搜两个图中的点的对应关系
本来想试试数据，结果AC了
```
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100 + 5;
const int INF = 1000000000;

struct Node{
int x, y;
};

Node g1[9], g2[9];
int f[9], vis[9];
int tot;

void init(){
string line;
for (int i = 0; i < 4; i++) {
cin >> line;
for (int j = 0; j < 4; j++) if (!(line[j] - '0')) {
g1[tot].x = i;
g1[tot].y = j;
tot++;
}
}
tot = 0;
for (int i = 0; i < 4; i++) {
cin >> line;
for (int j = 0; j < 4; j++) if (!(line[j] - '0')) {
g2[tot].x = i;
g2[tot].y = j;
tot++;
}
}
}

int ans = INF;
void dfs(int x, int d){
for (int i = 0; i < 8; i++) if (!vis[i]) {
f[x] = i; vis[i] = 1;
int t = abs(g1[x].x-g2[i].x)+abs(g1[x].y-g2[i].y);
//if (d+t >= ans) return;
if (x < 7) dfs(x+1, d+t);
else ans = min (ans, d+t);
vis[i] = 0;
}
}

int main(){
freopen ( "in.txt" , "r" , stdin);
init();
dfs(0,0);
cout << ans;
return 0;
}
```

找出需要移动的点。用数组把每个需要移动的点到目标点的距离存起来。DFS
不用位运算。

#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int a[20], b[20];
char aa[20], bb[20];
int fx[4] = {-1, 1, -4, 4};
int two[17] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536};
queue <int> q;
int hash[10000001];
int change(int *a) {
    int xx = 0;
    for(int i = 0; i < 16; i++)
        xx += two[15 - i] * a[i];
    return xx;
}
void scan(int *xx, char *x) {
    int l = strlen(x);
    for(int i = 0; i < 16 - l; i++)
        xx[i] = 0;
    for(int i = 0; i < 16; i++)
        xx[i + 16 - l] = x[i] - 48;
}
int main() {
    int s, t, xxxx, flag = 0;
    for(int i = 0; i < 4; i++) {
        cin >> xxxx;
        a[flag++] = xxxx / 1000;
        a[flag++] = (xxxx / 100) % 10;
        a[flag++] = (xxxx / 10) % 10;
        a[flag++] = xxxx % 10;
    }
    s = change(a);
    flag = 0;
    for(int i = 0; i < 4; i++) {
        cin >> xxxx;
        b[flag++] = xxxx / 1000;
        b[flag++] = (xxxx / 100) % 10;
        b[flag++] = (xxxx / 10) % 10;
        b[flag++] = xxxx % 10;
    }
    t = change(b);
    hash[s] = 1;
    q.push(s);
    while(!q.empty()) {
        char topc[20];
        memset(topc, 0, sizeof topc);
        int topi[20];
        if(q.front() == t)
            break;
        itoa(q.front(), topc, 2);
        scan(topi, topc);
        for(int i = 0; i < 16; i++)
            for(int j = 0; j < 4; j++) {
                if((i == 3 || i == 7 || i == 11) && j == 1) continue;
                if((i == 4 || i == 8 || i == 12) && j == 0) continue;
                if(i + fx[j] >= 0 && i + fx[j] < 16)
                    if(topi[i] != topi[i + fx[j]]) {
                        int tmp[20];
                        for(int k = 0; k < 16; k++)
                            tmp[k] = topi[k];
                        swap(tmp[i], tmp[i + fx[j]]);
                        int xxx = change(tmp);
                        if(hash[xxx] == 0) {
                            q.push(xxx), hash[xxx] = hash[q.front()] + 1;
                    }
                }
            }
        q.pop();
    }
    cout << hash[t] - 1 << endl;
    system("pause");
    return 0;
}

虽然是水题但依然刷了我半小时,位运算写的太丑陋了