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
十分感谢。