求助,90,#6 WA
查看原帖
求助,90,#6 WA
1240959
wither_ixg楼主2024/4/24 00:59

#6测试点:12,程序输出13

#include <bits/stdc++.h>

using namespace std;

struct point {
    int x = 0, y = 0;
    bool blocked = false;
    bool state = false;
    int dir = 0; // 0b1000...
    // get: dir & (1 << i) -> true: continue
    // set: dir ^= (1 << i)
} map_[51][51];

struct robot {
    int x = 0, y = 0;
    int facing = 0;
    int step = 0;
};

queue<robot> q;
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int ex, ey;

bool valid(int x, int y, int dir) {
    return (x > 0 && x < n) && (y > 0 && y < m) && !map_[x][y].blocked && !(map_[x][y].state && map_[x][y].dir & (1 << dir));
}

void bfs() {
    while(!q.empty()) {
        robot father = q.front();
        if(father.x == ex && father.y == ey) return;
        int l = 0;
        for(int i = 1; i <= 3; i++) {
            int cx = father.x + i * dx[father.facing];
            int cy = father.y + i * dy[father.facing];
            if(!valid(cx, cy, father.facing)) break;
            l = i;
        }
        for(int i = l; i >= 1; i--) {
            int cx = father.x + i * dx[father.facing];
            int cy = father.y + i * dy[father.facing];
            robot r;
            r.x = cx;
            r.y = cy;
            r.facing = father.facing;
            r.step = father.step + 1;
            q.push(r);
            point &p = map_[cx][cy];
            p.state = true;
            p.dir |= (1 << father.facing);
            if(r.x == ex && r.y == ey) return;
        }
        robot r;
        r.x = father.x;
        r.y = father.y;
        point &p = map_[r.x][r.y];
        r.facing = (father.facing + 4 + 1) % 4;
        if(valid(r.x, r.y, r.facing)) {
            p.state = true;
            p.dir |= (1 << r.facing);
            r.step = father.step + 1;
            q.push(r);
        }
        r.facing = (father.facing + 4 - 1) % 4;
        if(valid(r.x, r.y, r.facing)) {
            p.state = true;
            p.dir |= (1 << r.facing);
            r.step = father.step + 1;
            q.push(r);
        }
        q.pop();
    }
    robot r;
    r.step = -1;
    q.push(r);
}

int main() {
    robot r;
    cin >> n >> m;
    int x;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> x;
            if(x) {
                map_[i][j].blocked = true;
                map_[i + 1][j].blocked = true;
                map_[i][j + 1].blocked = true;
                map_[i + 1][j + 1].blocked = true;
            }
        }
    }
    cin >> r.x >> r.y >> ex >> ey;

    char f;
    cin >> f;
    switch(f) {
        case 'W':
            r.facing = 3;
            break;
        case 'S':
            r.facing = 0;
            break;
        case 'E':
            r.facing = 1;
            break;
        case 'N':
            r.facing = 2;
            break;
    }
    r.step = 0;
    q.push(r);
    bfs();
    cout << q.back().step;
    return 0;
}

2024/4/24 00:59
加载中...