当前位置：首页 > news >正文

（板子）A* astar算法，AcWing第k短路+八数码带注释

news 来源：原创 2024/4/27 12:11:00

第K短路

八数码

第K短路

给定一张 NN 个点（编号 1,2…N1,2…N），MM 条边的有向图，求从起点 SS 到终点 TT 的第 KK 短路的长度，路径允许重复经过点或边。

注意： 每条最短路中至少要包含一条边。

输入格式

第一行包含两个整数 NN 和 MM。

接下来 MM 行，每行包含三个整数 A,BA,B 和 LL，表示点 AA 与点 BB 之间存在有向边，且边长为 LL。

最后一行包含三个整数 S,TS,T 和 KK，分别表示起点 SS，终点 TT 和第 KK 短路。

输出格式

输出占一行，包含一个整数，表示第 KK 短路的长度，如果第 KK 短路不存在，则输出 −1−1。

数据范围

1≤S,T≤N≤10001≤S,T≤N≤1000,
0≤M≤1040≤M≤104,
1≤K≤10001≤K≤1000,
1≤L≤1001≤L≤100

输入样例：
2 2
1 2 5
2 1 4
1 2 2
输出样例：

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <queue>
#define x first;
#define y second
using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int N=1010,M=200010;
int n,m,S,T,K;
int h[N],rh[N],e[M],w[M],ne[M],idx;
int dist[N],cnt[N];//dist[i]表示点i到终点的估计值，也是最短距离，cnt[N]表示这个点已经是第几次到达了
bool st[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()//求返图最短路
{
    priority_queue<PII,vector<PII>,greater<PII> >heap;
    heap.push({0,T});//当前点到起点的距离，当前点
    memset(dist,0x3f,sizeof(dist));
    dist[T]=0;
    while(!heap.empty())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.y;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=rh[ver];i!=-1;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}});//三个值分别为估值函数的值=真实值+估计值，真实距离，当前遍历到哪个点
    while(!heap.empty())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.y.y,distance=t.y.x;
        cnt[ver]++;
        if(cnt[T]==K) return distance;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(cnt[j]<K)
            heap.push({distance+w[i]+dist[j],{distance+w[i],j}});
        }
    }
    return -1;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    memset(rh,-1,sizeof(rh));
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(h,a,b,c);
        add(rh,b,a,c);
    }
    scanf("%d%d%d",&S,&T,&K);
    if(S==T)
    K++;
    dijkstra();//对反向图求每个点到终点色的最短距离，求出估计值
    printf("%d\n",astar());
    return 0;
}

八数码

在一个 3×33×3 的网格中，1∼81∼8 这 88 个数字和一个 X 恰好不重不漏地分布在这 3×33×3 的网格中。

例如：
1 2 3
X 4 6
7 5 8
在游戏过程中，可以把 X 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 X
例如，示例中图形就可以通过让 X 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：
1 2 3   1 2 3   1 2 3   1 2 3
X 4 6   4 X 6   4 5 6   4 5 6
7 5 8   7 5 8   7 X 8   7 8 X
把 X 与上下左右方向数字交换的行动记录为 u、d、l、r。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入格式

输入占一行，将 3×33×3 的初始网格描绘出来。

例如，如果初始网格如下所示：
1 2 3 
x 4 6 
7 5 8 
则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。

如果答案不唯一，输出任意一种合法方案即可。

如果不存在解决方案，则输出 unsolvable。

输入样例：
2  3  4  1  5  x  7  6  8 
输出样例

ullddrurdllurdruldr

#include <bits/stdc++.h>
#include <cstring>
#include <unordered_map>
#include <queue>
using namespace std;
int f(string state)//计算当前状态的曼哈顿距离，作为估计值
{
    int res=0;
    for(int i=0;i<state.size();i++)
    if(state[i]!='x')
    {
        int t=state[i]-'1';
        res+=abs(i/3-t/3)+abs(i%3-t%3);
    }
    return res;
}
string bfs(string start)
{
    int dx[4]={-1,0,1,0};
    int dy[4]={0,1,0,-1};
    char op[4]={'u','r','d','l'};
    string end="12345678x";
    unordered_map<string ,int>dist;
    unordered_map<string,pair<string,char> > prev;//当前状态是通过前一个字符串的某个操作转移过来的
    priority_queue<pair<int,string>,vector<pair<int,string>>,greater<pair<int,string > > >heap;
    heap.push({f(start),start});
    dist[start]=0;//dist是准确值，不断被更新
    while(!heap.empty())
    {
        auto t=heap.top();
        heap.pop();
        string state=t.second;
        if(state==end)
        break;
        int step=dist[state];
        int x,y;
        for(int i=0;i<state.size();i++)//寻找x的位置
        {
            if(state[i]=='x')
            {
                x=i/3;
                y=i%3;
                break;
            }
        }
        string source=state;
        for(int i=0;i<4;i++)//遍历四个方向
        {
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3)
            {
                swap(state[x*3+y],state[a*3+b]);
                if(!dist.count(state)||dist[state]>step+1)
                {
                    dist[state]=step+1;
                    prev[state]={source,op[i]};
                    heap.push({dist[state]+f(state),state});
                }
                swap(state[x*3+y],state[a*3+b]);
            }
        }
    }
    string res;
    while(end!=start)//组合答案
    {
        res+=prev[end].second;
        end=prev[end].first;
    }
    reverse(res.begin(),res.end());
    return res;
}
int main()
{
    string g,c,seq;
    while(cin>>c)
    {
        g+=c;
        if(c!="x") seq+=c;
    }
    int t=0;
    for(int i=0;i<seq.size();i++)//查找逆序对
    {
        for(int j=i+1;j<seq.size();j++)
        {
            if(seq[i]>seq[j])
            t++;
        }
    }
    if(t%2) puts("unsolvable");
    else cout<<bfs(g)<<endl;
    return 0;
}