1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| #include<iostream> #include <queue> #include <cstring>
using namespace std; using ll = long long; #define endl '\n'
template<typename T=int> inline T read() { T x; cin >> x; return x; }
const int maxn = 110; bool book[maxn][maxn]; int G[maxn][maxn]; int M, N; int fx[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; struct Node { int x, y, z; Node *pre; };
void bfs(int sx, int sy, int ex, int ey) {//O(m*n) int ans = 0; queue<Node> Q; Q.push({sx, sy, 0}); book[sx][sy] = true; while (Q.size()) { auto &pt = Q.front(); int x = pt.x; int y = pt.y; int z = pt.z; if (x == ex && y == ey) { cout << z << endl; return; } Q.pop(); for (auto &i: fx) { int nx = x + i[0]; int ny = y + i[1]; if (nx < 1 nx > M ny < 1 ny > N book[nx][ny] G[nx][ny] == 1)continue; book[nx][ny] = true; Q.push({nx, ny, z + 1}); book[nx][ny] = 1; } } cout << "No Way!" << endl; }
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int ex, ey, sx, sy; while (cin >> M >> N) { memset(book, 0, sizeof(book)); for (int i = 1; i <= M; i++) for (int j = 1; j <= N; j++) { cin >> G[i][j]; } cin >> sx >> sy >> ex >> ey;
bfs(sx, sy, ex, ey); } return 0; }
|