88分求调(第一个点MLE,朴素的BFS做法)
包关注的
其实是我自己交了20多次还没做出来
#include <bits/stdc++.h>
using namespace std;
int mp[11][11], dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int n, m, sx, sy, fx, fy, ans = 0x7f7f7f7f, mx, my;
queue<pair<pair<int, int> , pair<int, int> > > q;
void bfs(int x, int y, int z, int cnt) {
q.push(make_pair(make_pair(x, y), make_pair(z, cnt)));
while (!q.empty()) {
int tx = q.front().first.first;
int ty = q.front().first.second;
int& mou = q.front().second.first;
int step = q.front().second.second;
if (mou == 0 || step > ans || step > m * n) {
q.pop();
continue;
}
if (mp[tx][ty] == 4) {
mou = 6;
}
if (tx == fx && ty == fy) {
ans = min(ans, step);
q.pop();
continue;
}
for (int i = 0; i < 4; i++) {
int mx = tx + dx[i];
int my = ty + dy[i];
if (mx < 1 || my < 1 || mx > n || my > m || mp[mx][my] == 0) {
continue;
}
q.push(make_pair(make_pair(mx, my), make_pair(mou - 1, step + 1)));
}
q.pop();
}
return;
}
int main(void) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mp[i][j];
if (mp[i][j] == 2) {
sx = i, sy = j;
}
if (mp[i][j] == 3) {
fx = i, fy = j;
}
}
}
bfs(sx, sy, 6, 0);
if (ans == 0x7f7f7f7f) {
cout << -1;
} else cout << ans;
return 0;
}