Cysheper @ 2024-09-17 16:11:47
/*
author:Cysheper
*/
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
#define y1 hhhhhhh
string a[1001];
int n, x1, y1, x2, y2;
struct node
{
int x, y, stp;
node(int gx, int gy, int gs) {
x = gx; y = gy; stp = gs;
}
};
bool check(int x, int y) {
if (x > n || y > n) return false;
if (x < 1 || y < 1) return false;
if (a[x - 1][y - 1] == '1') return false;
return true;
}
int bfs(int x, int y) {
queue<node> q;
q.push(node(x, y, 0));
while (!q.empty()) {
node ans = q.front();
q.pop();
if (ans.x == x2 && ans.y == y2) {
return ans.stp;
}
a[ans.x - 1][ans.y - 1] = '1';
if (check(ans.x + 1, ans.y)) q.push(node(ans.x + 1, ans.y, ans.stp + 1));
if (check(ans.x, ans.y + 1)) q.push(node(ans.x, ans.y + 1, ans.stp + 1));
if (check(ans.x, ans.y - 1)) q.push(node(ans.x, ans.y - 1, ans.stp + 1));
if (check(ans.x - 1, ans.y)) q.push(node(ans.x - 1, ans.y, ans.stp + 1));
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
cin >> x1 >> y1 >> x2 >> y2;
cout << bfs(x1, y1);
return 0;
}
by Cysheper @ 2024-09-17 18:00:54
已AC,此贴结