Two-way wide search
1 Two-way wide search
As the name suggests, it is bfs from the starting point and the end point at the same time, and stops until they meet
Can reduce exponential time complexity to linear exponential
String transformation
Title 
https://www.acwing.com/problem/content/description/192/ 
#include <bits/stdc++.h>
using namespace std;
const int N=6;
string a[N],b[N];
int n;
int extend(queue<string> & amp; q, unordered_map<string, int> & amp; da, unordered_map<string, int> & amp; db, string a[], string b[])
{
string t=q. front();
q. pop();
for(int i=0;i<t. size();i++)
{
for(int j=0;j<n;j++)
{
if(t.substr(i,a[j].size())==a[j])
{
string state=t.substr(0,i) + b[j] + t.substr(i + a[j].size());
if(db.count(state)) return da[t] + db[state] + 1;
if(da.count(state))continue;
da[state]=da[t] + 1;
q. push(state);
}
}
}
return 11;
}
int bfs(string A, string B)
{
if(A==B) return 0;
queue<string> qa,qb;
unordered_map<string,int> da,db;
qa.push(A),da[A]=0;
qb.push(B),db[B]=0;
while(qa. size() & amp; & amp; qb. size())
{
int t;
if(qa.size()<=qb.size()) t=extend(qa,da,db,a,b);
else t=extend(qb,db,da,b,a);
if(t<=10) return t;
}
return 11;
}
int main()
{
string A,B;
cin>>A>>B;
while(cin>>a[n]>>b[n])n + + ;
int step = bfs(A,B);
if(step>10)cout<<"NO ANSWER!";
else cout<<step;
}
Annotated version (for newcomers)
#include <bits/stdc++.h>
using namespace std;
const int N = 6;
int n;
string a[N],b[N];
// extension function
// Parameters: extended queue, distance to start point, distance to end point, rule, rule
//Return value: the minimum number of steps that satisfy the condition
int extend(queue<string> & amp; q, unordered_map<string,int> & amp; da, unordered_map<string, int> & amp; db,
string a[], string b[]){
// remove the head element
string t = q. front();
q. pop();
for(int i = 0; i < t.size(); i ++ ) // where does t start expanding
for(int j = 0; j < n; j ++ ) // enumeration rules
//If a section of the string t = rules, such as = xyz, it can be replaced
if(t.substr(i, a[j].size()) == a[j]){
// The result state after transformation: the previous unchanged part + the changed part + the latter unchanged part
// For example, abcd, according to the rule abc--> xu, becomes xud, and the state here is xud
string state = t.substr(0,i) + b[j] + t.substr(i + a[j].size());
// Whether the state state falls into b, the two directions meet, and return the minimum number of steps
if(db.count(state)) return da[t] + 1 + db[state];
// If the state has been expanded before,
if(da. count(state)) continue;
da[state] = da[t] + 1;
q. push(state);
}
return 11;
}
// do bfs from start and end
int bfs(string A, string B){
if(A==B) return 0;
queue<string> qa, qb; // queue in both directions
//The distance from each state to the starting point da (hash table), the distance from each state to the end point db hash table
unordered_map<string, int> da, db;
// qa starts searching from the starting point, qb starts searching from the end point
qa.push(A), da[A] = 0; // The distance from the starting point A to the starting point is 0
qb.push(B), db[B] = 0; // The distance from the end point B to the end point B is 0
// Both qa and qb have values, indicating that they can be extended, otherwise they are disjoint
while(qa. size() & amp; & amp; qb. size()){
int t; // record the minimum number of steps
// The length of the queue in which direction is smaller and the space is smaller, and it starts to expand from this direction,
// The time complexity is relatively smooth, otherwise one point will time out
if(qa. size() <= qb. size())
t = extend(qa, da, db, a, b);
else t = extend(qb, db, da, b, a);
// If the minimum number of steps is within 10 steps
if( t <= 10) return t;
}
return 11; // If not connected or the minimum number of steps > 10, return a number greater than 10
}
int main(){
string A, B;
cin >> A >> B;
// Read in the extension rules, there are a array and b array respectively
while( cin >> a[n] >> b[n]) n + + ;
int step = bfs(A,B);
if(step > 10) puts("NO ANSWER!");
else cout << step << endl;
}
A*
The A star algorithm is rarely used, but it is also an optimization of bfs
1. Eight digits
Title https://www.acwing.com/problem/content/description/181/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,string> pis;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int f(string a)//Used to find the estimated function, that is, the distance from this point to the end point
{
int dist=0;
for(int i=0;i<a.size();i + + )//Use the distance between two points to find
if(a[i]!='x')
{
int t=a[i]-'1';
dist + =abs(i/3-t/3) + abs(i%3-t%3);
}
return dist;
}
string bfs(string start)
{
string end="12345678x";
char op[]="urdl";//Up, left, down, right is a direction
unordered_map<string,int> d;//Used to find the distance
unordered_map<string,pair<char,string>> pre;//used to record track
priority_queue<pis,vector<pis>,greater<pis>> heap;//used to store distance and points
d[start]=0;
heap.push({f(start),start});
while(heap. size())
{
auto t=heap. top();
heap. pop();
string state=t.y;
if(state==end) break;//If it has been found, jump out directly
int x,y;
for(int i=0;i<9;i ++ )//find the position of x
if(state[i]=='x')
{
x=i/3,y=i%3;
break;
}
string source=state;
for(int i=0;i<4;i ++ )//Transfer in four directions
{
int a=x + dx[i],b=y + dy[i];
if(a<0||a>=3||b<0||b>=3) continue;//out of bounds continue
state=source;
swap(state[x*3 + y],state[a*3 + b]);//Exchange the position, which is the new state
if(d.count(state)==0||d[state]>d[source] + 1)//If the state has not been updated, or there is a shorter distance
{
d[state]=d[source] + 1;//Then update the shortest distance
pre[state]={op[i],source};//Record who converted it and the conversion method
heap.push({f(state) + d[state],state});
}
}
}
string ans;
while(end!=start)//Record track backwards
{
ans + =pre[end].x;
end=pre[end].y;
}
reverse(ans.begin(), ans.end());//Reverse it
return ans;//return track
}
int main()
{
string start;
char c;
while(cin>>c) start + =c;
int cnt=0;
for(int i=0;i<9;i ++ )//find the number of reverse pairs
{
if(start[i]=='x') continue;
for(int j=i;j<9;j++)
if(start[i]>start[j]) cnt + + ;
}
if(cnt & amp;1) puts("unsolvable");//If the reverse pair is odd, there is no answer
else cout<<bfs(start)<<endl;//Conversely, bfs again
return 0;
}
2. Kth short circuit
Title https://www.acwing.com/problem/content/180/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
const int N=1010, M=2e5 + 10;
int n,m,S,T,K;
int h[N],rh[N],e[M],w[M],ne[M],idx;
int dist[N];
bool st[N];
int cnt[N];
void add(int h[],int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx + + ;
}
void dijkstra()//Use dijkstra to find the valuation function f[i]
{
priority_queue<pii, vector<pii>, greater<pii>> heap;
heap.push({0,T});
memset(dist,0x3f,sizeof dist);
dist[T]=0;
while(heap. size())
{
auto t=heap. top();
heap. pop();
int ver=t.y;
if(st[ver]) continue;
st[ver]=true;
for(int i=rh[ver];~i;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[ver] + w[i])
{
dist[j]=dist[ver] + w[i];
heap.push({dist[j],j});
}
}
}
}
int astar()
{
priority_queue<piii, vector<piii>, greater<piii>>heap;
heap.push({dist[S],{0,S}});
//whose d[u] + f[u] is smaller and who goes out of the queue first
while(heap. size())
{
auto t=heap. top();
heap. pop();
int ver=t.y.y,distance=t.y.x;
cnt[ver] + + ;
if(cnt[T]==K) return distance; //If the end point has been visited k times, then the ver at this time is the end point T and return the answer
for(int i=h[ver];~i;i=ne[i])
{
int j=e[i];
/*
If cnt[j]>=K at an intermediate point, it means that j has been out of the team k times, and astar() has no return distance,
It means that starting from j, the kth short circuit cannot be found (let the end point go out of the queue k times),
That is, if you continue to let j join the team, there is still no solution.
Then there is no need to let j continue to join the team
*/
if(cnt[j]<K)
{
// Press true value + estimated value = d[j] + f[j]
heap.push({distance + w[i] + dist[j],{distance + w[i],j}});
}
}
}
// The endpoint has not been visited k times
return -1;
}
int main()
{
memset(h,-1, sizeof h);
memset(rh,-1, sizeof rh);
cin>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(h,a,b,c);
add(rh,b,a,c);//Used to reverse the distance
}
cin>>S>>T>>K;
if(S==T) K ++ ;
dijkstra();
cout<<astar()<<endl;
return 0;
}