codeforces 908 B New Year and Buggy Bot

codeforces 908 B New Year and Buggy Bot

(​​ B. New Year and Buggy Bot time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Bob programmed a robot to navigate through a 2d maze.

The maze has some obstacles. Empty cells are denoted by the character ‘.’, where obstacles are denoted by ‘#’.

There is a single robot in the maze. It’s start position is denoted with the character ‘S’. This position has no obstacle in it. There is also a single exit in the maze. It’s position is denoted with the character ‘E’. This position has no obstacle in it.

The robot can only move up, left, right, or down.

When Bob programmed the robot, he wrote down a string of digits consisting of the digits 0 to 3, inclusive. He intended for each digit to correspond to a distinct direction, and the robot would follow the directions in order to reach the exit. Unfortunately, he forgot to actually assign the directions to digits.

The robot will choose some random mapping of digits to distinct directions. The robot will map distinct digits to distinct directions. The robot will then follow the instructions according to the given string in order and chosen mapping. If an instruction would lead the robot to go off the edge of the maze or hit an obstacle, the robot will crash and break down. If the robot reaches the exit at any point, then the robot will stop following any further instructions.

Bob is having trouble debugging his robot, so he would like to determine the number of mappings of digits to directions that would lead the robot to the exit. Input

The first line of input will contain two integers n and m (2 ≤ n, m ≤ 50), denoting the dimensions of the maze.

The next n lines will contain exactly m characters each, denoting the maze.

Each character of the maze will be ‘.’, ‘#’, ‘S’, or ‘E’.

There will be exactly one ‘S’ and exactly one ‘E’ in the maze.

The last line will contain a single string s (1 ≤ |s| ≤ 100) — the instructions given to the robot. Each character of s is a digit from 0 to 3. Output

Print a single integer, the number of mappings of digits to directions that will lead the robot to the exit. Examples Input

5 6 …..# S….# .#…. .#…. …E.. 333300012

Output

1

Input

6 6 …… …… ..SE.. …… …… …… 01232123212302123021

Output

14

Input

5 3 … .S.

#

.E. … 3

Output

0

Note

For the first sample, the only valid mapping is , where D is down, L is left, U is up, R is right.

给定一张图 给定起点终点 再给定操控的过程 但是操控操作方法和他所对应的UP DOWN LEFT RIGHT 并非一一对应 所以我需要暴力枚举 题目中给的3 2 1 0到底哪一个代表向上走 向右走 然后确定了这种方案之后我需要按照题目中给出的操作 来模拟一下这个过程看最终有多少方案可以走到终点

#include#includeint dx[]={-1,0,1,0},dy[]={0,1,0,-1},n,m,ans,mp[5],len,stx,sty,edx,edy;char s[55][55],order[55];inline void gao(){ int x=stx,y=sty; for (int i=1;i<=len;++i){ x+=dx[mp[order[i]-'0']];y+=dy[mp[order[i]-'0']]; if (x<1||x>n||y<1||y>m||s[x][y]=='#') return; if (x==edx&&y==edy) {++ans;return;} }}int main(){// freopen("cfb.in","r",stdin); scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%s",s[i]+1); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) { if (s[i][j]=='S') stx=i,sty=j;if (s[i][j]=='E') edx=i,edy=j; } scanf("%s",order+1);len=strlen(order+1); for (int i=0;i<4;++i){ for (int j=0;j<4;++j){ if (i==j) continue; for (int k1=0;k1<4;++k1){ if (k1==i||k1==j) continue; for (int k2=0;k2<4;++k2){ if (k2==i||k2==j||k2==k1) continue; mp[i]=0;mp[j]=1;mp[k1]=2;mp[k2]=3; gao(); } } } }printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。