cf97D. Robot in Basement(模拟 bitset)

题意

题目链接

Sol

接下来我的实现方式和论文里不太一样

然后用bitset优化，上下走分别对应着右移/左移m位，左右走对应着右移/左移1位

我们可以直接预处理出能走的格子和不能走的格子，每次走的时候先全都走过去，再把撞到墙上的补回来即可

#include<bits/stdc++.h>

#define u32 unsigned int

using namespace std;

const int MAXN = 1e5 + 10, SS = 150 * 150 + 150;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, M, Len, id;

bitset<SS> now, B, can;

char s[151], str[MAXN];

int main() {

    N = read(); M = read(); Len = read();

    for(int i = 1; i <= N; i++) {

        scanf("%s", s + 1);

        for(int j = 1; j <= M; j++) {

            if(s[j] == '#') B[i * M + j] = 1;

            else can[i * M + j] = now[i * M + j] = 1;

            if(s[j] == 'E') id = i * M + j;

        }

    }

    scanf("%s", str + 1);

    if(now.count() == 1 && now[id] == 1) return puts("0"), 0;

    for(int i = 1; i <= Len; i++) {

        if(str[i] == 'U') {

            now = ((now >> M) & can) | (now & (B << M));

        } else if(str[i] == 'D') {

            now = ((now << M) & can) | (now & (B >> M));

        } else if(str[i] == 'L') {

            now = ((now >> 1) & can) | (now & (B << 1));

        } else if(str[i] == 'R') {

            now = ((now << 1) & can) | (now & (B >> 1));

        }

        if(now.count() == 1 && now[id] == 1) {

            printf("%d\n", i);

            return 0;

        }

    }

    puts("-1");

    return 0;

}