2176: Robot in Basement
Time Limit: 2 Sec
Memory Limit: 256 MB
Submit: 9
Solved: 5
[Submit][Status][Web Board]
Description
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The Professor has lost his home robot yet again. After some thinking Professor understood that he had left the robot in the basement.
The basement in Professor's house is represented by a rectangle n×m, split into 1×1
Professor is scared of going to the dark basement looking for the robot at night. However, he has a basement plan and the robot's remote control. Using the remote, Professor can send signals to the robot to shift one square left, right, up or down. When the robot receives a signal, it moves in the required direction if the robot's neighboring square in the given direction is passable. Otherwise, the robot stays idle.
Professor wrote a sequence of k
Executing each command takes some energy and Professor doesn't want to get huge electricity bill at the end of the month. That's why he wants to find in the sequence he has written out the minimal possible prefix that would guarantee to lead the robot out to the exit after the prefix is fulfilled. And that's the problem Professor challenges you with at this late hour.
Input
The first line contains three integers n, m and k (3≤n,m≤150, 1≤k≤105). Next n lines contain m characters each − that is the Professor's basement's description: "#" stands for a wall, "." stands for a passable square and "E" stands for the exit from the basement (this square also is passable). It is possible to get from each passable square to the exit, all squares located by the n×m rectangle's perimeter are the walls. Exactly one square is the exit from the basement. The last line contains k characters, the description of the sequence of commands that Professor has written out on a piece of paper. "L", "R", "U", "D" stand for commands left, right, up and down correspondingly.
Output
Print in the output file the length of the smallest possible prefix that will lead the robot to the exit square. In other words, wherever the robot had been positioned initially, it should be positioned in the exit square after all
Examples
Input
5 5 7
#####
#...#
#...#
#E..#
#####
UULLDDR
Output
6
Input
5 5 7
#####
#.#.#
#...#
#E..#
#####
UULLDDR
Output
-1
Input
5 3 2
###
#.#
#.#
#E#
###
DD
Output
2
【分析】
模拟....因為并不需要知道一個點有幾個機器人，隻要知道這個點有沒有機器人就可以了....暴力模拟肯定t了
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
char s[100005];
int n, m, k;
int work(){
bitset<23000> a, b, c, e;
for(int i = 0; i < n; i++)
{
scanf("%s", s);
for(int j = 0; j < m; j++)
{
(s[j]=='#'?b:a).set(i*m+j);
(s[j]=='E'?e.set(i*m+j):0);
}
}
scanf("%s", s);
c = a;
for(int i = 0; i < k; i++)
{
if(c==e)return i;
if(s[i]=='U') c = ((c>>m)&a) | (c&(b<<m));
if(s[i]=='L') c = ((c>>1)&a) | (c&(b<<1));
if(s[i]=='D') c = ((c<<m)&a) | (c&(b>>m));
if(s[i]=='R') c = ((c<<1)&a) | (c&(b>>1));
}
if(c==e)return k;
return -1;
}
int main(){
int i, j;
while (~scanf("%d %d %d", &n, &m, &k)){
printf("%d\n", work());
}
return 0;
}