题目大意：一个数字通过每个位+1 -1 和旁边的交换，最后达到目标状态的最少步数。
单搜：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int vis[10000];
int v[10000][2];
bool found;
int tag;
struct node
{
int t[4];
int step;
};
int get(node e)
{
int h=0;
for(int i=0;i<4;i++)
h=(h * 10) + e.t[i];
//printf("%d\n",h);
return h;
}
void mark(queue<node> &Q,bool flag,node e,int state)
{
if(flag)
{
if(v[state][0]!=1)
{
if(v[state][0]==2)
{
printf("%d\n",e.step + v[state][1]);
found = true;
return;
}
v[state][0]=1;
v[state][1]=e.step;
Q.push(e);
}
}
else
{
if(v[state][0]!=2)
{
if(v[state][0]==1)
{
printf("%d\n",e.step + v[state][1]);
found = true;
return;
}
v[state][0]=2;
v[state][1]=e.step;
Q.push(e);
}
}
}
void expend(queue<node> &Q,bool flag)
{
node w,e;
w=Q.front();
Q.pop();
for(int i=0;i<=3;i++)
{
e=w;
int state;
e.t[i]++;
if(e.t[i]==10)e.t[i]=1;
e.step = w.step + 1;
state = get(e);
mark(Q,flag,e,state);
if(found)return;
}
for(i=0;i<=3;i++)
{
e=w;
int state;
e.t[i]--;
if(e.t[i]==0)e.t[i]=9;
e.step = w.step + 1;
state = get(e);
mark(Q,flag,e,state);
if(found)return;
}
for(i=0;i<=2;i++)
{
e=w;
int state;
swap(e.t[i],e.t[i+1]);
e.step =w.step + 1;
state = get(e);
mark(Q,flag,e,state);
if(found)return;
}
}
void bfs(node start,node end)
{
found = false;
queue<node>Q1;
queue<node>Q2;
Q1.push(start);
Q2.push(end);
while(!Q1.empty() || !Q2.empty())
{
if(!Q1.empty())
expend(Q1,true);
if(found)
return;
if(!Q2.empty())
expend(Q2,false);
if(found)
return;
}
}
void BFS(node t)
{
queue<node>Q;
node w,e;
Q.push(t);
while(!Q.empty())
{
w=Q.front();
Q.pop();
for(int i=0;i<=3;i++)
{
e=w;
e.t[i]++;
if(e.t[i]==10)e.t[i]=1;
if(vis[get(e)]==0){
e.step++;
if(get(e)==tag){printf("%d\n",e.step);return;}
vis[get(e)]=1;
Q.push(e);}
}
for(i=0;i<=3;i++)
{
e=w;
e.t[i]--;
if(e.t[i]==0)e.t[i]=9;
if(vis[get(e)]==0){
e.step++;
if(get(e)==tag){printf("%d\n",e.step);return;}
vis[get(e)]=1;
Q.push(e);}
}
for(i=0;i<=2;i++)
{
e=w;
swap(e.t[i],e.t[i+1]);
if(vis[get(e)]==0)
{
e.step++;
if(get(e)==tag){printf("%d\n",e.step);return;}
vis[get(e)]=1;
Q.push(e);
}
}
}
}
int main()
{
int test;
char str[5];
node start , end;
scanf("%d",&test);
while(test--)
{
//memset(v,0,sizeof(v));
memset(vis,0,sizeof(vis));
scanf("%s",str);
for(int i=0;i<4;i++)
start.t[i]=str[i]-'0';
scanf("%s",str);
for(i=0;i<4;i++)
end.t[i]=str[i]-'0';
tag=get(end);
/* v[get(start)][0]=1;
v[get(start)][1]=0;
v[get(end)][0]=2;
v[get(end)][1]=0;*/
if(get(start)==get(end)){printf("0\n");continue;}
vis[get(start)]=1;
start.step=0;
BFS(start);
//printf("%d\n",get(end));
//bfs(start,end);
//putchar(10);
}
return 0;
}
双搜：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int v[10000];
bool found;
int ans1;
int ans2;
struct node
{
int t[4];
int step;
};
int get(node e)
{
int h=0;
for(int i=0;i<4;i++)
h=(h * 10) + e.t[i];
return h;
}
void mark(queue<node> &Q,bool flag,node e,int state)
{
if(flag)
{
if(v[state]!=1)
{
if(v[state]==2)
{
found = true;
return;
}
v[state]=1;
Q.push(e);
}
}
else
{
if(v[state]!=2)
{
if(v[state]==1)
{
found = true;
return;
}
v[state]=2;
Q.push(e);
}
}
}
void expend(queue<node> &Q,bool flag)
{
node w,e;
w=Q.front();
Q.pop();
for(int i=0;i<=3;i++)
{
e=w;
int state;
e.t[i]++;
if(e.t[i]==10)e.t[i]=1;
e.step++;
state = get(e);
mark(Q,flag,e,state);
if(found)return;
}
for(int i=0;i<=3;i++)
{
e=w;
int state;
e.t[i]--;
if(e.t[i]==0)e.t[i]=9;
e.step++;
state = get(e);
mark(Q,flag,e,state);
if(found)return;
}
for(int i=0;i<=2;i++)
{
e=w;
int state;
swap(e.t[i],e.t[i+1]);
e.step++;
state = get(e);
mark(Q,flag,e,state);
if(found)return;
}
}
void bfs(node start,node end)
{
found = false;
queue<node>Q1;
queue<node>Q2;
Q1.push(start);
Q2.push(end);
while(!Q1.empty() || !Q2.empty())
{
int tmp=Q1.front().step;
while(!Q1.empty())
{
if(Q1.front().step != tmp)break;
ans1=tmp+1;
expend(Q1,true);
}
if(found)
{
printf("%d\n",ans1+ans2);
return;
}
tmp=Q2.front().step;
while(!Q2.empty())
{
if(Q2.front().step != tmp)break;
ans2=tmp+1;
expend(Q2,false);
}
if(found)
{
printf("%d\n",ans1+ans2);
return;
}
}
}
int main()
{
int test;
char str[5];
node start , end;
scanf("%d",&test);
while(test--)
{
memset(v,0,sizeof(v));
scanf("%s",str);
for(int i=0;i<4;i++)
start.t[i]=str[i]-'0';
scanf("%s",str);
for(int i=0;i<4;i++)
end.t[i]=str[i]-'0';
v[get(start)]=1;
ans1=0;
v[get(end)]=2;
ans2=0;
if(get(start)==get(end)){printf("0\n");continue;}
start.step=0;
end.step =0;
bfs(start,end);
}
return 0;
}