cf97D. Robot in Basement(模拟 bitset)
程序员文章站
2022-05-07 07:56:49
题意 "题目链接" Sol 接下来我的实现方式和论文里不太一样 然后用bitset优化,上下走分别对应着右移/左移m位,左右走对应着右移/左移1位 我们可以直接预处理出能走的格子和不能走的格子,每次走的时候先全都走过去,再把撞到墙上的补回来即可 ......
题意
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; }
上一篇: 我们走!
下一篇: 看,我抓到了一只茄子精