109徐守佳

用户名：dotcpp0787174

访问量：1092

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	884
经　　验	3544
参赛次数	3
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

[信息学奥赛一本通T1547-区间和]-分块写法
浏览：19

你可能喜欢

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

A star/A * 路径规划算法

　　作者: 109徐守佳　　　　发表时间：2024-09-13 18:46:41 浏览：22　|　评论：1　

原题链接：蓝桥杯历届试题-九宫重排

# A star/A * 路径规划算法
## 曼哈顿距离介绍: [详情](https://baike.baidu.com/item/%E6%9B%BC%E5%93%88%E9%A1%BF%E8%B7%9D%E7%A6%BB/743092 "详情")
曼哈顿距离是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。****也就是红线代表曼哈顿距离****
![](/image_editor_upload/20240913/20240913062935_36951.png)
# AC代码
```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N = 1e6 + 10,M = 2 * 1e4 + 10,inf = 0x3f3f3f3f;

typedef pair<int,string> PIS;

string endd,start;
unordered_map<string,int> dist; //记录状态和所用步数
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; //方向数组
int f(string str) 
//估价函数-用于计算所有点到终点对应位置的曼哈顿距离之和
{
    int res = 0;
    for(int i=0;i<str.size();i++)
    {
        if(str[i]!='.')
        {
            int t = str[i] - '1';
            res += (abs(i/3 - t/3) + abs(i%3 - t%3)); 
            //计算所有曼哈顿距离之和 
        }
    }
    return res;
}
bool bfs(string start,string end)
{
	if(start == end) return true; //起点就是终点就返回true
	
    priority_queue<PIS,vector<PIS>,greater<PIS>> heap; 
    //按所有状态的曼哈顿距离之和放入优先队列(优先拿距离最小的状态)
    heap.push({f(start),start});
    dist[start] = 0;
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        string state = t.second;
        int x,y;
        for(int i=0;i<state.size();i++)
        {
            if(state[i]=='.')
            {
                x = i / 3;
                y = i % 3;
                // 找到空位的一维坐标转化为二维坐标
            }
        }
        string soure = state; //存储字符串,后面有用
        for(int i=0;i<4;i++)
        {
            int a = x + dir[i][0] , b = y + dir[i][1];
            if(a < 0 || b < 0 || a >= 3 || b >= 3) continue;
            state = soure; //复原state，循环可能会导致state变化
            swap(state[a*3 + b],state[x*3 + y]); 
			//二维转化回一维
            if(dist.count(state)==0 || dist[state] > dist[soure] + 1)
            {
                // 如果达到这个状态所需步数更小，则需要优化这个步数
                dist[state] = dist[soure] + 1;
                if(state == end) return true; 
				// 达到目标状态退出函数返回true
                heap.push({f(state) + dist[state],state});
                //加入当前步数+估价函数值的和
            }
        }
    }
	//未找到返回false
	return false;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>start>>endd;
	
	if(bfs(start,endd))
    cout<<dist[endd]<<endl; //输出最终状态的步数
	else cout<<"-1"<<endl;
	
    return 0;
}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

yxy

%%% orz

2024-09-17 01:02:22

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

【回文数(二)】（C语言代码）

C语言考试练习题_排列（C++代码）

矩阵转置（C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

A star/A * 路径规划算法

评论区

精彩推荐

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【绝对值排序】（C语言代码）

【计算两点间的距离】（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1908题解

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

数字游戏（C++代码）

1048题解（读入回车问题）

数组与指针的问题

printf基础练习（C语言代码）

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

【回文数(二)】 （C语言代码）

C语言考试练习题_排列 （C++代码）

矩阵转置 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

A star/A * 路径规划算法

评论区

精彩推荐

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【绝对值排序】 （C语言代码）

【计算两点间的距离】 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1908题解

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

数字游戏 （C++代码）

1048题解（读入回车问题）

数组与指针的问题

printf基础练习 （C语言代码）

【回文数(二)】（C语言代码）

C语言考试练习题_排列（C++代码）

矩阵转置（C语言代码）

　　评论区

【绝对值排序】（C语言代码）

【计算两点间的距离】（C语言代码）

数字游戏（C++代码）

printf基础练习（C语言代码）