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;
}