题目描述
Bob 对机器人进行了编程，让它在平面迷宫中行走。
迷宫有一些障碍。 空单元格由字符"."表示，障碍物由"#"表示。
迷宫中只有一个机器人。 它的起始位置用字符"S"表示。 这个位置没有任何障碍。 迷宫中也只有一个出口，用字符"E"表示。 这个位置没有任何障碍。
机器人只能向上、向左、向右或向下移动。
Bob 给机器人编程时，写下了一串整数，由1,2,3,4其中若干个组成。 他打算让每个数字对应一个不同的方向，机器人会按照指示到达出口。 不幸的是，他忘记了每个数字分配的是什么方向。
机器人会自动将1,2,3,4随机映射到不同方向，然后按照给定的指令顺序进行操作。如果指令导致机器人离开迷宫边缘或撞到障碍物，机器人就会崩溃。如果机器人在任意时刻到达出口，那么机器人将停止且不执行后续指令。
Bob 想确定有多少种不同的方向映射方案能够将机器人到达出口。
输入格式
第一行输入两个整数 n 和 m，表示迷宫行数和列数。
接下来的 n 行每行恰好包含 m 个字符，表示迷宫。
迷宫中的每个字符都是".", "#", "S"或"E"。
迷宫中将恰好有一个"S"和一个"E"。
最后一行将包含一个字符串s ，表示给机器人的指令。
输出格式
输出一个整数，表示能够让机器人到达出口的方向映射方案数。
样例
样例输入1
5 6
.....#
S....#
.#....
.#....
...E..
333300012
样例输出1
1
样例输入2
6 6
......
......
..SE..
......
......
......
01232123212302123021
样例输出2
14
这道题肯定用搜索
首先四个数不同方向肯定要用到全排列
所以先把全排列的代码写出来
void dfs(int step){
for(int i=0;i<4;i++){
if(vis[i]==0){
vis[i]=1;
q[step]=i;
dfs(step+1);
vis[i]=0;
}
}
}然后有了全排列，这道题就好做了，接下来就是按照输入的指令来模拟就行了。
首先在输入地图的时候就找好起点S的位置，然后把指令遍历一遍，用方向数组移动就行了
注意边界判断，x<1,y<1,x>n,y>m的时候都不行，还有遇到障碍物a[x][y]=='#'的时候，直接return
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,m;
char a[N][N];
struct node{
int x,y;
}first;
string s;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int q[4]={0,0,0,0};
bool vis[4];
int len;
int sum;
void dfs(int step){
if(step==4){
int fx=first.x,fy=first.y;
for(int i=0;i<len;i++){
fx+=dx[q[s[i]-'0']];
fy+=dy[q[s[i]-'0']];
if(fx>n||fy>m||fx<1||fy<1||a[fx][fy]=='#')return;
if(a[fx][fy]=='E'){
sum++;
return;
}
}
}
for(int i=0;i<4;i++){
if(vis[i]==0){
vis[i]=1;
q[step]=i;
dfs(step+1);
vis[i]=0;
}
}
}
signed main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
scanf("%c",&a[i][j]);
if(a[i][j]=='S'){
first.x=i;
first.y=j;
}
}
}
cin>>s;
len=s.length();
dfs(0);
printf("%d",sum);
}
