MLE*9 求调,玄关

P1746 离开中山路

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,此贴结


|