BFS WA#27,马蜂良好求调
查看原帖
BFS WA#27,马蜂良好求调
22716
神仙酱楼主2024/7/17 16:33
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10, INF = 0x3f3f3f3f;

int n, m, sx, sy, l, r;
char mp[N][N];
int st[N][N];
int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
struct state_t {
    int x, y, l, r;
};
int bfs() {
    queue<state_t> q;
    q.push({ sx, sy, l, r });
    int cnt = 0;
    while (q.size()) {
        auto [x, y, wl, wr] = q.front();
        q.pop();
        if (exchange(mp[x][y], '+') == '+' && st[x][y] >= wl + wr)
            continue;
        st[x][y] = wl + wr;
        cnt++;
        for (int i = 0; i < 4; ++i) {
            int xx = x + dx[i], yy = y + dy[i];
            if (0 < xx && xx <= n && 0 < yy && yy <= m && mp[xx][yy] != '*') {
                int new_wl = wl, new_wr = wr;
                new_wl -= i == 3;
                new_wr -= i == 2;
                if (new_wl >= 0 && new_wr >= 0)
                    q.push({ xx, yy, new_wl, new_wr });
            }
        }
    }
    return cnt;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
#else
    cin.tie(0)->sync_with_stdio(0);
#endif
    cin >> n >> m >> sx >> sy >> l >> r;
    cin.get();
    for (int i = 1; i <= n; ++i) {
        cin.getline(mp[i] + 1, m + 1);
    }
    memset(st, 0x3f, sizeof st);
    cout << bfs() << "\n";
    return 0;
}

2024/7/17 16:33
加载中...