GreenInsect

用户名：dotcpp0716004

访问量：70

签　名：

等　　级
排　　名	30333
经　　验	502
参赛次数	0
文章发表	1
年　　龄	20
在职情况	学生
学　　校	门头沟学院
专　　业	马克思主义哲学

　　自我简介：

TA的其他文章

题解 2172: 信息学奥赛一本通T1330-最少步数：A*搜索算法
浏览：35

你可能喜欢

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

题解 2172: 信息学奥赛一本通T1330-最少步数：A*搜索算法

　　作者: GreenInsect　　　　发表时间：2024-02-10 16:21:14 浏览：35　|　评论：0　

原题链接：信息学奥赛一本通T1330-最少步数

# A*搜索算法

**A*算法 , 我认为就是用估价函数和堆优化过的BFS**
**以下是AC代码（为毛是绿色的 ， 第一次用Markdown不会嘞）**

```cpp
	#include<iostream>
	#include<queue>
	#include<bitset>
	#include<cmath>
	#include<cstring>
	using namespace std;
	const int maxn = 150 ;
	bool chess[maxn][maxn];
	int dx[12] = {-2,-2,2,2,-1,-2,-2,-1,1,2,2,1};
	int dy[12] = {-2,2,2,-2,-2,-1,1,2,2,1,-1,-2};
	struct Sta{
		int x , y;
	    int step , exp;
	};
	void h(Sta &sta){       //估价函数，计算当前点到终点的曼哈顿距离
	    int x = sta.x , y = sta.y;
	    sta.exp = fabs(x - 1) + fabs(y - 1) ;
	    return ;
	}
	struct cmp{               //堆（优先队列）用到的仿函数
	    bool operator() (Sta &s1 , Sta &s2){
 	       return (s1.exp + s1.step) > (s2.exp + s2.step) ;
 	   }
	};

int A_Star(Sta &start){              //代码主体
		memset(chess , 0 , sizeof(chess)); 
		//这边有个小细节，因为要计算两个起点，所以每次都要初始化一遍
	    priority_queue<Sta , vector<Sta> , cmp > sq;
	    h(start);
	    sq.push(start);
	    while(sq.size()){
 	       Sta t = sq.top();
  	      sq.pop();
  	      chess[t.x][t.y] = true;
  	      if(t.x == 1 && t.y == 1){
 	  	         return t.step;
 	       }
   		     for(int i = 0 ; i < 12 ; ++i){
    	        if(t.x + dx[i] >= 1 && t.y + dy[i] >= 1 && t.x + dx[i] <= 100 && t.y + dy[i] <= 100 && chess[t.x + dx[i]][t.y + dy[i]] == false){
 	  	             Sta ne;
    	            ne.x = t.x + dx[i] , ne.y = t.y + dy[i];
     	           ne.step = t.step + 1;
      	          h(ne);
      	          sq.push(ne);
     	       }
    	    }
  	  }
	}

int main(){

int x1 , y1 , x2 , y2;
   	 cin >> x1 >> y1 >> x2 >> y2 ;
   	 Sta s1{x1 ,y1} , s2{x2 , y2};
  	  cout << A_Star(s1) << endl << A_Star(s2) << endl;
  	  return 0;
	}
```

0.0分

0 人评分

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

GreenInsect

TA的其他文章

你可能喜欢

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

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

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

C二级辅导-等差数列（C语言代码）

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

题解 2172: 信息学奥赛一本通T1330-最少步数：A*搜索算法

评论区

精彩推荐

程序员的表白（C语言代码）

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

不容易系列2 （C语言代码）

拆分位数（C语言代码）

妹子杀手的故事（C语言代码）

大神老白（C语言代码）

【偶数求和】（C语言代码）

淘淘的名单（C语言代码）

【蟠桃记】（C语言代码）

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

GreenInsect

TA的其他文章

你可能喜欢

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

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

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

C二级辅导-等差数列 （C语言代码）

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

题解 2172: 信息学奥赛一本通T1330-最少步数 ：A*搜索算法

评论区

精彩推荐

程序员的表白 （C语言代码）

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

不容易系列2 （C语言代码）

拆分位数 （C语言代码）

妹子杀手的故事 （C语言代码）

大神老白 （C语言代码）

【偶数求和】 （C语言代码）

淘淘的名单 （C语言代码）

【蟠桃记】 （C语言代码）

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

C二级辅导-等差数列（C语言代码）

题解 2172: 信息学奥赛一本通T1330-最少步数：A*搜索算法

　　评论区

程序员的表白（C语言代码）

拆分位数（C语言代码）

妹子杀手的故事（C语言代码）

大神老白（C语言代码）

【偶数求和】（C语言代码）

淘淘的名单（C语言代码）

【蟠桃记】（C语言代码）