求助大佬,想用A*算法和优先队列优化一下,但是不知道哪里错了
  • 板块P1605 迷宫
  • 楼主xuan132
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/12/25 09:50
  • 上次更新2023/10/28 13:43:57
查看原帖
求助大佬,想用A*算法和优先队列优化一下,但是不知道哪里错了
582113
xuan132楼主2021/12/25 09:50
#include<cstdio>
#include<queue>
#include <math.h>
#include<cstring>
using namespace std;
int n,m,k,x,y,a,b,ans;
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
bool vis[6][6];
struct oo{
    int x,y,used[6][6];
    int step,abbs;//step是走过步数的统计,abbs是当前位置与终点曼哈顿距离 
    bool operator<(const oo x)
    const{
    	return (this->abbs+this->step)<(x.abbs+x.step);
	}
};
void bfs()
{
	oo sa;
    priority_queue<oo> q;     
    sa.x = x;
    sa.y = y;         
    sa.used[x][y] = 1;
    q.push(sa);
    while(!q.empty())
    {
        oo now = q.top();    
        q.pop();
        for(int i = 0;i < 4; i++)
        {
            int sx = now.x + dx[i];
            int sy = now.y + dy[i];
            if( now.used[sx][sy] 
                || vis[sx][sy] 
                || sx == 0 || sy == 0 
                || sx > n || sy > m)
                continue;    //如果这里走过,或者这里是障碍,或者这里是墙壁,那么这里就不能走。
            if(sx == a && sy == b)
            {
                ans++;           
                continue;
            }
            sa.x = sx;
            sa.y = sy;
            memcpy(sa.used,now.used,sizeof(now.used));
            sa.used[sx][sy] = 1;    
            sa.step++;
            sa.abbs=abs(a-sx)+abs(b-sy);
            q.push(sa);
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d%d%d",&x,&y,&a,&b);      
    for(int i = 1,aa,bb;i <= k; i++)   
    {
        scanf("%d%d",&aa,&bb);         
        vis[aa][bb] = 1;
    }
    bfs();
    printf("%d",ans);
    return 0;
}
2021/12/25 09:50
加载中...