請問A*不就是按照曼哈頓距離去當作優先權算嗎?
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define dis(a,b) abs(a-b)
using namespace std;
char maze[1001][1001];
int l[1001][1001];
struct pos
{
int x,y;
int distance=-1;
};
struct cmp
{
bool operator()(pos a,pos b)
{
// return 0;
if(a.distance!=b.distance) return a.distance<b.distance;
return l[a.x][a.y]<l[b.x][b.y];
}
} ;
void astar(int x,int y,int tx,int ty,int t)
{
int move[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
if(maze[x][y]=='X'||maze[tx][ty]=='X')
{
cout<<"ERROR\n";
return;
}
l[x][y]=1;
pos p;
p.x=x;
p.y=y;
p.distance=dis(x,tx)+dis(y,ty);
priority_queue<pos,vector<pos>,cmp> pq;
pq.push(p);
while(!pq.empty())
{
p=pq.top();
if(p.x==tx&&p.y==ty) break;
int k=l[p.x][p.y];
pq.pop();
rep(i,4)
{
pos p2;
int x2=p.x+move[i][0];
int y2=p.y+move[i][1];
if(x2>=0&&x2<t&&y2>=0&&y2<t)
{
if(!l[x2][y2]&&maze[x2][y2]!='X')
{
l[x2][y2]=k+1;
p2.x=x2;
p2.y=y2;
p2.distance=dis(tx,x2)+dis(ty,y2);
pq.push(p2);
}
else l[x2][y2]=min(l[x2][y2],k+1);
}
}
}
cout<<l[tx][ty]-1<<"\n";
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
rep(i,n)
rep(j,n) cin>>maze[i][j];
while(m--)
{
memset(l,0,sizeof(l));
int x,y,x2,y2;
cin>>x>>y>>x2>>y2;
astar(x,y,x2,y2,n);
}
}
請問A*不就是按照曼哈頓距離去當作優先權算嗎?
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define dis(a,b) abs(a-b)
using namespace std;
char maze[1001][1001];
int l[1001][1001];
struct pos
{
int x,y;
int distance=-1;
};
struct cmp
{
bool operator()(pos a,pos b)
{
// return 0;
if(a.distance!=b.distance) return a.distance<b.distance;
return l[a.x][a.y]<l[b.x][b.y];
}
} ;
void astar(int x,int y,int tx,int ty,int t)
{
int move[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
if(maze[x][y]=='X'||maze[tx][ty]=='X')
{
cout<<"ERROR\n";
return;
}
l[x][y]=1;
pos p;
p.x=x;
p.y=y;
p.distance=dis(x,tx)+dis(y,ty);
priority_queue<pos,vector,cmp> pq;
pq.push(p);
while(!pq.empty())
{
p=pq.top();
if(p.x==tx&&p.y==ty) break;
int k=l[p.x][p.y];
pq.pop();
rep(i,4)
{
pos p2;
int x2=p.x+move[i][0];
int y2=p.y+move[i][1];
if(x2>=0&&x2<t&&y2>=0&&y2<t)
{
if(!l[x2][y2]&&maze[x2][y2]!='X')
{
l[x2][y2]=k+1;
p2.x=x2;
p2.y=y2;
p2.distance=dis(tx,x2)+dis(ty,y2);
pq.push(p2);
}
else l[x2][y2]=min(l[x2][y2],k+1);
}
}
}
cout<<l[tx][ty]-1<<"\n";
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
rep(i,n)
rep(j,n) cin>>maze[i][j];
while(m--)
{
memset(l,0,sizeof(l));
int x,y,x2,y2;
cin>>x>>y>>x2>>y2;
astar(x,y,x2,y2,n);
}
}
找到問題了