题目描述
有一个 n×m 个单元格构成的迷宫,其中空单元格用 . 表示,障碍物用 # 表示。
迷宫中有一个机器人,它的起点位置用 S 表示,目标位置用 E 表示,这两个地点均没有障碍。
机器人只能沿上下左右四个方向移动。
给定一串由数字 0∼3 构成的字符串,表示机器人的行动指令列表。
机器人将按照列表中的指令,依次进行移动。
在执行指令的过程中:
如果机器人走出迷宫边界或者碰到障碍物,则机器人会损坏。
如果机器人到达目标位置,则停止行动,不再接受后续指令。
现在,哪个数字(0∼3)对应哪种行动(上下左右)还未分配。
请问,共有多少种分配方案,能够使得机器人顺利到达目标位置。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含两个整数 n 和 m。
接下来 n 行,每行包含 m 个字符,表示迷宫。所有字符均为 ., #, S, E 之一,其中 S 和 E 出现且仅出现一次。
最后一行包含一个字符串 s 表示指令列表,每个字符均为 0∼3 之一。
输出格式
每组数据输出一行结果,表示能够使得机器人顺利到达目标位置的行动指令分配方案数量。
数据范围
前三个测试点满足 2≤n,m≤10。
所有测试点满足 1≤T≤10,2≤n,m≤50,1≤|s|≤100。
同一测试点内,所有 n×m 的和不超过 2500。
样例
输入样例:
2
5 6
.....#
S....#
.#....
.#....
...E..
333300012
6 6
......
......
..SE..
......
......
......
01232123212302123021
输出样例:
1
14
算法1
(暴力枚举) $O()$
1.先找出0-4所有可能的排列
2.依次check
时间复杂度
参考文献
python3 代码
from typing import List
#---- 获取0-4的所有排列
def get_permutation(n: int) -> List[List[int]]:
def backtrace(idx: int) -> int:
nonlocal res
nonlocal path
if idx == n:
res.append(path[:])
return
for x in range(n):
if visited[x] == False:
visited[x] = True
path.append(x)
backtrace(idx + 1)
path.pop()
visited[x] = False
res = []
visited = [False for _ in range(4)]
path = []
backtrace(0)
return res
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
dis_permutation = get_permutation(4)
T = int(input())
for _ in range(T):
Row, Col = map(int, input().split())
mat = []
for _ in range(Row):
mat.append(list(input()))
order = input()
#----找起点和终点坐标
sr, sc = -1, -1 #起点坐标
er, ec = -1, -1 #终点坐标
for r in range(Row):
for c in range(Col):
if mat[r][c] == 'S':
sr, sc = r, c
elif mat[r][c] == 'E':
er, ec = r, c
#----check当前的方向分配方式,能否到达终点
def check(dis: List[int]) -> bool:
r, c = sr, sc
for x in order:
di = dis[int(x) - 0]
dr, dc = dirs[di]
nr = r + dr
nc = c + dc
if not(0 <= nr < Row and 0 <= nc < Col and mat[nr][nc] != '#'):
return False
elif nr == er and nc == ec:
return True
else:
r, c = nr, nc
return False
#----尝试所有的方向赋值方式
res = 0
for dis in dis_permutation:
if check(dis) == True:
res += 1
print(res)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int Row; //行数
int Col; //列数
string order; //指令
int sr, sc; //起点
int er, ec; //终点
//----check当前赋值方式下,能否到达终点
bool check(vector<int> dis, vector<vector<char>> mat)
{
int r = sr, c = sc;
for (char & cc : order)
{
int di = dis[cc - '0'];
int dr = dirs[di][0], dc = dirs[di][1];
int nr = r + dr;
int nc = c + dc;
if (!(0 <= nr && nr < Row && 0 <= nc && nc < Col && mat[nr][nc] != '#'))
return false;
else if (nr == er && nc == ec)
return true;
else
r = nr, c = nc;
}
return false;
}
int main()
{
int T; cin >> T;
while (T --)
{
cin >> Row;
cin >> Col;
vector<vector<char>> mat(Row, vector<char>(Col));;
for (int r = 0; r < Row; r ++)
for (int c = 0; c < Col; c ++)
cin >> mat[r][c];
cin >> order; //指令
//----找起点和终点
for (int r = 0; r < Row; r ++)
{
for (int c = 0; c < Col; c ++)
{
if (mat[r][c] == 'S')
sr = r, sc = c;
if (mat[r][c] == 'E')
er = r, ec = c;
}
}
//----尝试左右的方向赋值方式
int res = 0;
vector<int> dis {0, 1, 2, 3};
for (int _ = 0; _ < 24; _ ++)
{
if (check(dis, mat) == true)
res ++;
next_permutation(dis.begin(), dis.end());
}
cout << res << endl;
}
return 0;
}
java 代码
import java.util.* ;
public class Main
{
static int [][] dirs = new int [][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int N = 50;
static char [][] mat = new char [N][N];
static int Row; //行数
static int Col; //列数
static String order = new String(); //指令
static int sr, sc; //起点
static int er, ec; //终点
public static void main(String args [])
{
List<List<Integer>> dis_permutation = get_permutation(4); //0-4的所有排列
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
while (T -- > 0)
{
Row = scan.nextInt(); //输入行数
Col = scan.nextInt(); //输入列数
for (int r = 0; r < Row; r ++)
{
String line = scan.next();
for (int c = 0; c < Col; c ++)
{
mat[r][c] = line.charAt(c);
}
}
order = scan.next(); //输入指令
//----找起点和终点
for (int r = 0; r < Row; r ++)
{
for (int c = 0; c < Col; c ++)
{
if (mat[r][c] == 'S')
{
sr = r;
sc = c;
}
if (mat[r][c] == 'E')
{
er = r;
ec = c;
}
}
}
//----尝试所有方向的负值排列
int res = 0;
for (List<Integer> dis : dis_permutation)
{
if (check(dis) == true)
res ++;
}
System.out.println(res);
}
}
public static boolean check(List<Integer> dis)
{
int r = sr, c = sc;
char [] order_arr = order.toCharArray();
for (char ch : order_arr)
{
int di = dis.get(ch - '0');
int dr = dirs[di][0], dc = dirs[di][1];
int nr = r + dr;
int nc = c + dc;
if (!(0 <= nr && nr < Row && 0 <= nc && nc < Col && mat[nr][nc] != '#'))
return false;
else if (nr == er && nc == ec)
return true;
else
{
r = nr;
c = nc;
}
}
return false;
}
//----------------------- 求所有的排列
static List<List<Integer>> res_per = new ArrayList<>();
static List<Integer> path_per = new ArrayList<>();
static boolean [] visited = new boolean [4];
public static List<List<Integer>> get_permutation(int n)
{
backtrace(0, n);
return res_per;
}
public static void backtrace(int idx, int n)
{
if (idx == n)
{
res_per.add(new ArrayList<>(path_per));
return ;
}
for (int x = 0; x < n; x ++)
{
if (visited[x] == false)
{
visited[x] = true;
path_per.add(x);
backtrace(idx + 1, n);
path_per.remove(path_per.size() - 1);
visited[x] = false;
}
}
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla