MVP_Harry @ 2020-05-22 07:31:07
我一看这不是一道BFS板子题吗,但一直RE,非常困惑,求大佬解惑
#include<bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for(int i = m; i <= n; i++)
int n, vis[10005][10005], sx, sy, ex, ey, ans;
char mp[10005][10005];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct node {
int x, y, dis;
};
void bfs(int x, int y) {
vis[x][y] = 1;
queue<node> q;
q.push((node){x, y, 0});
while (!q.empty()) {
node temp = q.front();
q.pop();
rep(i, 0, 4) {
int xx = temp.x + dx[i], yy = temp.y + dy[i];
if (!vis[xx][yy] && xx >= 0 && xx <= n - 1 && yy >= 0 && yy <= n - 1 && mp[xx][yy] == '0') {
vis[xx][yy] = 1;
q.push((node){xx, yy, temp.dis + 1});
}
}
if (temp.x == ex - 1 && temp.y == ey - 1) {
ans = temp.dis;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
cout << n << endl;
rep(i, 0, n - 1) {
cin >> mp[i];
}
cin >> sx >> sy >> ex >> ey;
bfs(sx - 1, sy - 1);
cout << ans << endl;
return 0;
}
by MVP_Harry @ 2020-05-22 07:32:37
对了,我现在这个版本开的都是10005,但其实题目理论只需要1005就可以了,但10005还是RE了qwq
by iMya_nlgau @ 2020-05-22 08:07:51
@MVP_Harry
bfs()里那个rep(i, 0, 4)
应该是rep(i, 0, 3)
by MVP_Harry @ 2020-05-22 08:42:04
@Sapphire6575737973 有道理,我平时一般用rep(i, 1, 4)的qwq
by MVP_Harry @ 2020-05-22 08:42:22
不够现在全WA了哈哈哈
by JohnVictor @ 2020-05-22 08:45:33
ans = temp.dis;
改成 ans=min(ans,temp.dis)
,然后 ans
赋初值 inf
试试
by MVP_Harry @ 2020-05-22 09:10:25
@JohnVictor bfs为什么需要这个啊?
by MVP_Harry @ 2020-05-22 09:13:37
@JohnVictor 而且还是全WA,我怀疑我BFS写错了。。。
by MVP_Harry @ 2020-05-22 09:28:20
卧槽我知道怎么错了,多输出了一个n
by JohnVictor @ 2020-05-22 10:04:35
emmmmmm