欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

cf97D. Robot in Basement(模拟 bitset)

程序员文章站 2022-05-07 07:56:49
题意 "题目链接" Sol 接下来我的实现方式和论文里不太一样 然后用bitset优化,上下走分别对应着右移/左移m位,左右走对应着右移/左移1位 我们可以直接预处理出能走的格子和不能走的格子,每次走的时候先全都走过去,再把撞到墙上的补回来即可 ......

题意

题目链接

cf97D. Robot in Basement(模拟 bitset)

sol

cf97D. Robot in Basement(模拟 bitset)

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

然后用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;
}