A*
P1379 Wah Rong Road
The problem is to use the minimum number of steps from the initial layout to the target layout. Each time you can only move the grid around 0, which is Huarong Road;
How to solve it using algorithmic ideas?
State compression ideas
Each number represents the current state. Both the queue and map functions record the current state number.
Describing a state has a matrix form and a numerical form
Here c[3][3] is the matrix describing the state, and n is the number describing the state.
Here, n is converted into matrix form, and the position of 0 in the matrix is obtained, recorded with f and g.
The exchange operation cannot be performed in numbers and is relatively abstract, so it is necessary to convert it into a matrix, try the exchange in the matrix, and then convert it back to the form of numbers for storage after the exchange is completed, in order to save space. ns means that the current matrix is moved according to the current traversal order. The final result is,
If it does not appear in the Map, it means that this number (this state) does not exist in the Map, which means it is a newly arrived state. Since it is bfs, it must be the minimum number of steps to reach this state.
#include<iostream>
#include<map>
#include<queue>
#include<algorithm>
#define ll long long//I saw a very cool operation here: directly define int as long long; the main function uses signed type - Mom is no longer afraid that I forget to open long long!
using namespace std;
const ll dx[]={-1,0,0,1},dy[]={0,-1,1,0};//Transfer array;
ll n;
int main()
{
cin>>n;
queue<ll> q;
q.push(n);
map<ll,ll> m;
m[n]=0;
while(!q.empty())
{
int u=q.front(); //Initial state is queued
int c[3][3],f=0,g=0,n=u;q.pop();
if(u==123804765)break;
for(ll i=2;i>=0;i--)
for(ll j=2;j>=0;j--)
{
c[i][j]=n ,n/=10;
if(!c[i][j])f=i,g=j;
}
for(ll i=0;i<4;i + + )
{
ll nx=f + dx[i],ny=g + dy[i],ns=0;
if(nx<0||ny<0||nx>2||ny>2)continue; //out of bounds will not be executed
swap(c[nx][ny],c[f][g]);
for(ll i=0;i<3;i + + )
for(ll j=0;j<3;j + + )ns=ns*10 + c[i][j];//Matrix to sequence
if(!m.count(ns))
{
m[ns]=m[u] + 1; //map removes duplicates and counts the number of steps required to reach this state.
q.push(ns);
}
swap(c[nx][ny],c[f][g]);//State restoration
}
}
cout<<m[123804765]<<endl; // The subscript of the map is directly represented by the sequence
return 0;
}
map
map search
map operation function
The commonly used count() returns the number of occurrences, int type, returns the number of occurrences of the key, not the value corresponding to the key, so it can only be 0 or 1
If it is !m.count(n), it means that it is triggered when it is not found, that is, there is no key n in the map at this time.
m.count(n) means that this element has been found, that is, there is already n element in the map.
A* method
This step is to determine whether the current state is still a possible solution. step is the current step number, cnt is the valuation function value. The determination of the value of cnt involves a double cycle. Once it is detected that the solution in the current grid is different, It will + + cnt, this loops 9 times, or if it exceeds the limit while in the loop, it will exit.
This is to determine whether the current solution is
That is to say, pre is to record the last time you came here The direction mark at the time means that you should not go back. If you do, go up (down) first and then down (up). Go left (right) first and then right (left).
The state movement array can be manually defined so that the sequence numbers in opposite directions have a certain relationship.
Here is a symmetric array arrangement, Thus, the sum of the serial numbers in the opposite direction is the array length – 1
Therefore, in the recursive judgment, it is necessary to judge pre + i==3, pre is the previous direction, and i is the direction selected this time. If the sum is 3, it means that we have gone back and need to be cut off.
Although this operation cannot avoid the birth of infinite loops, such as back-shaped loops, or the emergence of repeated states (avoiding repeated states that only require two steps, but may return to the initial position in multiple steps), it can still avoid a large number of two-steps. repeat
Here is the input string (status compression sequence) into a matrix and get the position of 0
K is used as the outer loop, that is, it is directly based on the step limit to determine whether it can be reached currently.
#include<iostream>
#include<string>
#include<map>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long <;
int read()
{
int f=1,x=0;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0' & amp; & amp;ss<='9'){x=x*10 + ss-'0';ss=getchar();}
return f*x;
}
char ss[15];
int ans[4][4]=
{<!-- -->{0,0,0,0},
{0,1,2,3},
{0,8,0,4},
{0,7,6,5}};
int a[5][5],k,judge;
int nxtx[]={0,1,-1,0};
int nxty[]={1,0,0,-1};
int check()
{
for(int i=1;i<=3; + + i)
for(int j=1;j<=3; + + j)
if(ans[i][j]!=a[i][j])return 0;
return 1;
}
int test(int step)
{
int cnt=0;
for(int i=1;i<=3; + + i)
for(int j=1;j<=3; + + j)
if(ans[i][j]!=a[i][j]){ if( + + cnt + step>k) return 0;}
return 1;
}
void A_star(int step,int x,int y,int pre)
{
if(step==k){ if(check())judge=1; return;}The maximum depth of the current limit is reached
if(judge) return;
for(int i=0;i<4; + + i)
{
int nx=x + nxtx[i],ny=y + nxty[i];
if(nx<1||nx>3||ny<1||ny>3||pre + i==3) continue; //Added the above optimal pruning
swap(a[x][y],a[nx][ny]);
if(test(step) & amp; & amp;!judge) A_star(step + 1,nx,ny,i);//A* valuation is legal and then search downwards
swap(a[x][y],a[nx][ny]);
}
}
int main()
{
int x,y;
scanf("%s", & amp;ss);
for(int i=0;i<9; + + i)
{
a[i/3 + 1][i%3 + 1]=ss[i]-'0';
if(ss[i]-'0'==0)x=i/3 + 1,y=i%3 + 1;
}
if(check()){printf("0");return 0;}//Special judgment does not require movement
while( + + k)//Enumeration maximum depth
{
A_star(0,x,y,-1);
if(judge){printf("%d",k);break;}
}
return 0;
}