lygmh @ 2019-02-13 13:36:52

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
//#define baorong
#define ll long long
using namespace std;
struct br {
    int x;
    int y;
    int step;
};
br queuen[1000001];
int u[4] = { 1,-1, 0, 0 };
int v[4] = { 0, 0, 1,-1 };
int m;
int ans;
int f1x, f2x, f1y, f2y;
int px[1000001];
int py[1000001];
int p;
char map[1002][1002];
bool used1[1002][1002];
bool used2[1002][1002];
bool flag;
int result1[1002][1002];
int result2[1002][1002];
bool is_place(int x, int y) {
    if (x < 0 || y < 0 || x >= m || y >= m) {
        return false;
    } else {
        return true;
    }
}
int l, r;
void bfs1() {
    l = 1;
    r = 1;
    queuen[1].x = f1x;
    queuen[1].y = f1y;
    queuen[1].step = 0;
    result1[queuen[1].x][queuen[1].y] = queuen[1].step;
    used1[queuen[1].x][queuen[1].y] = true;
    while (l <= r) {
        if(map[queuen[l].x][queuen[l].y]=='0') {
            for (int i = 0; i < 4; i++) {
                if ((is_place(queuen[l].x + u[i], queuen[l].y + v[i]))&&(!used1[queuen[l].x + u[i]][queuen[l].y + v[i]]) ) {
                    r++;
                    queuen[r].x = queuen[l].x + u[i];
                    queuen[r].y = queuen[l].y + v[i];
                    queuen[r].step = queuen[l].step + 1;
                    used1[queuen[r].x][queuen[r].y]=true;
#ifdef baorong
                    cout<<queuen[r].x<<" "<<queuen[r].y<<"#"<<endl;
#endif
                    result1[queuen[r].x][queuen[r].y] = queuen[r].step;
                }
            }
        }

        l++;
    }
}
void bfs2() {
    l = 1;
    r = 1;
    queuen[1].x = f2x;
    queuen[1].y = f2y;
    queuen[1].step = 0;
    result2[queuen[1].x][queuen[1].y] = queuen[1].step;
    used2[queuen[1].x][queuen[1].y] = true;
    while (l <= r) {
        if(map[queuen[l].x][queuen[l].y]=='0') {
            for (int i = 0; i < 4; i++) {
                if ( (is_place(queuen[l].x + u[i], queuen[l].y + v[i]))&& (!used2[queuen[l].x + u[i]][queuen[l].y + v[i]])) {
                    r++;
                    queuen[r].x = queuen[l].x + u[i];
                    queuen[r].y = queuen[l].y + v[i];
                    queuen[r].step = queuen[l].step + 1;
                    used2[queuen[r].x][queuen[r].y]=true;
#ifdef baorong
                    cout<<queuen[r].x<<" "<<queuen[r].y<<"#"<<endl;
#endif
                    result2[queuen[r].x][queuen[r].y] = queuen[r].step;
                }
            }
        }

        l++;
    }
}
int main() {
    cin >> m ;
    for (int i = 0; i < m; i++) {
        cin >> map[i];
        for (int j = 0; j < m; j++) {
            if (map[i][j] == '1') {
                px[p] = i;
                py[p] = j;
                p++;
            }
        }
    }
    cin>>f1x>>f1y>>f2x>>f2y;
    f1x--;
    f1y--;
    f2x--;
    f2y--;
    bfs1();
    bfs2();
    ans = 0x7fff;
#ifdef baorong
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            cout<<result1[i][j]<<" ";
        }
        cout<<endl;
    }
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            cout<<result2[i][j]<<" ";
        }
        cout<<endl;
    }
#endif
    for (int i = 0; i < p; i++) {
        if(result1[px[i]][py[i]]&&result2[px[i]][py[i]]) {
            ans = min(result1[px[i]][py[i]] + result2[px[i]][py[i]], ans);
        }

    }
    cout << ans;
    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

额，前面那个的头文件...

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:57:05

对不起啊，我也不知道头文件怎么回事，你自己搞一下吧。

by litim @ 2019-02-13 13:58:21

@Caden
希望更丰富的展现？使用Markdown

by Caden @ 2019-02-13 14:02:14

嗯？

by Caden @ 2019-02-13 14:03:03

有啥事？

by Createsj @ 2019-02-13 14:03:30

@Caden 帮您修了下：

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:04:00

Emm...

by Caden @ 2019-02-13 14:12:31

谢谢。其实不用修也可以

有谁来加个团吗？

[MINECRAFT]

[Planet X]

by Caden @ 2019-02-13 14:13:43

加了打个招呼。