【Java版】dfs求排列+模拟
import java.io.*;
import java.util.*;
public class Main{
static String[][] mg;//迷宫
static int[] st = new int[2]; //起点
static int[] ed = new int[2];//终点
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t-->0){
String[] rec = br.readLine().split(" ");
int n = Integer.parseInt(rec[0]);
int m = Integer.parseInt(rec[1]);
mg = new String[n][m];//n行,m列
//读取输入
for(int i=0;i<n;i++){
mg[i] = br.readLine().split("");
for(int j=0;j<m;j++){
if(mg[i][j].equals("S")){
st[0] = i;
st[1] = j;
}
if(mg[i][j].equals("E")){
ed[0] = i;
ed[1] = j;
}
}
}
String con = br.readLine();//读取操作指令
dfs(0,"");//求所有的排列数,放在集合中
int[] dx = new int[]{-1,1,0,0};//行
int[] dy = new int[]{0,0,-1,1};//列
int ans = 0;//记录所有的结果数量
for(String s:set){
int[] temp = new int[]{st[0],st[1]};//起点
int[] arr = new int[4];//存储当前排列组合的数组
for(int i=0;i<4;i++){
arr[i] = s.charAt(i)-'0';
}
for(int i=0;i<con.length();i++){
int val = con.charAt(i)-'0';
temp[0] += dx[arr[val]];//行操作
temp[1] += dy[arr[val]];//列操作
//若越界或者碰到障碍物
if(temp[0]<0||temp[1]<0||temp[0]>=n||temp[1]>=m||mg[temp[0]][temp[1]].equals("#")){
break;
}
//若到达终点
if(temp[0] == ed[0] && temp[1] == ed[1]){
ans++;
break;
}
}
}
System.out.println(ans);
}
br.close();
}
//求0123能组成的所有排列【dfs做】
static HashSet<String> set = new HashSet<>();//存储所有排列结果
static boolean[] isUse = new boolean[4];//记录所有数字的遍历情况
public static void dfs(int index,String ans){
if(index == 4){
set.add(ans);
return;
}
for(int i=0;i<4;i++){
if(!isUse[i]){
isUse[i] = true;
dfs(index+1,ans+i);
isUse[i] = false;
}
}
}
}