求助大佬 80分

P1746 离开中山路

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 wxy_god @ 2019-02-13 14:14:06

希望更丰富的展现?使用Markdown


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

十分感谢。


上一页 |