看不懂你的思路，我就看了一下题，然后又写了一个：
#include<bits/stdc++.h>
using namespace std;
int n,bx,by,wx,wy,moves[4][2]= {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}, ans;
bool CL[1002][1002], OL[1002][1002];
char tmap[1002][1002];
struct node{
int x,y,step,f,h;
void init(int _x, int _y, int _step) {
x= _x;
y= _y;
step= _step;
h= abs(x - wx) + abs(y - wy);
f= step + h;
}
void update(int _step) {
step= _step;
f= step + h;
}
int abs(int _a) {
return _a > 0 ? _a : -_a;
}
} newn[1002][1002];
struct nodecmp {
bool operator()(node *&a, node *&b) const {
if(a->f == b->f) return a->h > b->h;
return a->f > b->f;
}
};
int lx, ly, lstep, newx, newy;
void Astar() {
priority_queue<node *, vector<node *>, nodecmp> q;
newn[bx][by].init(bx, by, 0);
q.push(&newn[bx][by]);
while(!q.empty()) {
lx= q.top()->x;
ly= q.top()->y;
lstep= q.top()->step;
q.pop();
CL[lx][ly]= true;
for(int i= 0; i < 4; i++) {
newx= lx + moves[i][0], newy= ly + moves[i][1];
if(tmap[newx][newy] == '1' || CL[newx][newy]) continue;
if(newx == wx && newy == wy) {
ans= lstep + 1;
return;
}
if(OL[newx][newy]) {
if(lstep < newn[newx][newy].step) {
newn[newx][newy].update(lstep + 1);
}
}
else {
newn[newx][newy].init(newx, newy, lstep + 1);
q.push(&newn[newx][newy]);
OL[newx][newy]= true;
}
}
}
return;
}
int main() {
cin >> n;
for(int i= 0; i <= n + 1; i++) {
for(int j= 0; j <= n + 1; j++) {
if(i == 0 || j == 0 || i == n + 1 || j == n + 1)
tmap[i][j]= '1';
else
cin >> tmap[i][j];
}
}
cin >> bx >> by >> wx >> wy;
Astar();
cout << ans << endl;
return 0;
}
by Caden @ 2019-02-13 13:54:40
额，前面那个的头文件...
#include<bits/stdc++.h>
using namespace std;
int n,bx,by,wx,wy,moves[4][2]= {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}, ans;
bool CL[1002][1002], OL[1002][1002];
char tmap[1002][1002];
struct node{
int x,y,step,f,h;
void init(int _x, int _y, int _step) {
x= _x;
y= _y;
step= _step;
h= abs(x - wx) + abs(y - wy);
f= step + h;
}
void update(int _step) {
step= _step;
f= step + h;
}
int abs(int _a) {
return _a > 0 ? _a : -_a;
}
} newn[1002][1002];
struct nodecmp {
bool operator()(node *&a, node *&b) const {
if(a->f == b->f) return a->h > b->h;
return a->f > b->f;
}
};
int lx, ly, lstep, newx, newy;
void Astar() {
priority_queue<node *, vector<node *>, nodecmp> q;
newn[bx][by].init(bx, by, 0);
q.push(&newn[bx][by]);
while(!q.empty()) {
lx= q.top()->x;
ly= q.top()->y;
lstep= q.top()->step;
q.pop();
CL[lx][ly]= true;
for(int i= 0; i < 4; i++) {
newx= lx + moves[i][0], newy= ly + moves[i][1];
if(tmap[newx][newy] == '1' || CL[newx][newy]) continue;
if(newx == wx && newy == wy) {
ans= lstep + 1;
return;
}
if(OL[newx][newy]) {
if(lstep < newn[newx][newy].step) {
newn[newx][newy].update(lstep + 1);
}
}
else {
newn[newx][newy].init(newx, newy, lstep + 1);
q.push(&newn[newx][newy]);
OL[newx][newy]= true;
}
}
}
return;
}
int main() {
cin >> n;
for(int i= 0; i <= n + 1; i++) {
for(int j= 0; j <= n + 1; j++) {
if(i == 0 || j == 0 || i == n + 1 || j == n + 1)
tmap[i][j]= '1';
else
cin >> tmap[i][j];
}
}
cin >> bx >> by >> wx >> wy;
Astar();
cout << ans << endl;
return 0;
}
by Caden @ 2019-02-13 13:55:56
对不起啊，我也不知道头文件怎么回事，你自己搞一下吧。
by Caden @ 2019-02-13 13:57:05
@[Caden](/space/show?uid=83807)
希望更丰富的展现？[使用Markdown](https://www.luogu.org/wiki/show?name=%E5%B8%AE%E5%8A%A9%EF%BC%9Amarkdown)
by litim @ 2019-02-13 13:58:21
嗯？
by Caden @ 2019-02-13 14:02:14
有啥事？
by Caden @ 2019-02-13 14:03:03
@[Caden](/space/show?uid=83807) 帮您修了下：
```cpp
include<bits/stdc++.h>
using namespace std;
int n,bx,by,wx,wy,moves[4][2]= {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}, ans;
bool CL[1002][1002], OL[1002][1002];
char tmap[1002][1002];
struct node{
int x,y,step,f,h;
void init(int _x, int _y, int _step) {
x= _x;
y= _y;
step= _step;
h= abs(x - wx) + abs(y - wy);
f= step + h;
}
void update(int _step) {
step= _step;
f= step + h;
}
int abs(int _a) {
return _a > 0 ? _a : -_a;
}
} newn[1002][1002];
struct nodecmp {
bool operator()(node *&a, node *&b) const {
if(a->f == b->f) return a->h > b->h;
return a->f > b->f;
}
};
int lx, ly, lstep, newx, newy;
void Astar() {
priority_queue<node *, vector<node *>, nodecmp> q;
newn[bx][by].init(bx, by, 0);
q.push(&newn[bx][by]);
while(!q.empty()) {
lx= q.top()->x;
ly= q.top()->y;
lstep= q.top()->step;
q.pop();
CL[lx][ly]= true;
for(int i= 0; i < 4; i++) {
newx= lx + moves[i][0], newy= ly + moves[i][1];
if(tmap[newx][newy] == '1' || CL[newx][newy]) continue;
if(newx == wx && newy == wy) {
ans= lstep + 1;
return;
}
if(OL[newx][newy]) {
if(lstep < newn[newx][newy].step) {
newn[newx][newy].update(lstep + 1);
}
}
else {
newn[newx][newy].init(newx, newy, lstep + 1);
q.push(&newn[newx][newy]);
OL[newx][newy]= true;
}
}
}
return;
}
int main() {
cin >> n;
for(int i= 0; i <= n + 1; i++) {
for(int j= 0; j <= n + 1; j++) {
if(i == 0 || j == 0 || i == n + 1 || j == n + 1)
tmap[i][j]= '1';
else
cin >> tmap[i][j];
}
}
cin >> bx >> by >> wx >> wy;
Astar();
cout << ans << endl;
return 0;
}
```
by Createsj @ 2019-02-13 14:03:30
Emm...
by Createsj @ 2019-02-13 14:04:00
谢谢。~~其实不用修也可以~~
有谁来加个团吗？
[[MINECRAFT]](https://www.luogu.org/team/show?teamid=13844)
[[Planet X]](https://www.luogu.org/team/show?teamid=13636)
by Caden @ 2019-02-13 14:12:31
加了打个招呼。
by Caden @ 2019-02-13 14:13:43