230513 第二次周考

XSC062 / 2023-05-13 / 原文

第一次周考被菌哥哥（白眼）吃了

A. 行走的机器人

http://222.180.160.110:1024/contest/3583/problem/1

不难想到用 std::next_permutation 解决方向问题，然后模拟走路过程判定。

复杂度 \(\mathcal O(24n^2)\)，其中 \(24=A_4^4\)。赛时耗时 14min。

namespace XSC062 {
using namespace fastIO;
const int maxn = 55;
const int maxm = 105;
const int fx[] = { 1, -1, 0, 0 };
const int fy[] = { 0, 0, 1, -1 };
int a[maxn];
char s[maxm];
char t[maxn][maxn];
int n, m, l, x, y, sx, sy, ex, ey, res;
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", t[i] + 1);
		for (int j = 1; j <= m; ++j) {
			if (t[i][j] == 'S')
				sx = i, sy = j;
			if (t[i][j] == 'E')
				ex = i, ey = j;
		}
	}
	scanf("%s", s + 1);
	l = strlen(s + 1);
	for (int i = 0; i < 4; ++i)
		a[i] = i;
	for (int i = 1; i <= 24; ++i) {
		x = sx, y = sy;
		for (int j = 1; j <= l; ++j) {
			x += fx[a[s[j] - '0']];
			y += fy[a[s[j] - '0']];
			if (x < 1 || y < 1 || x > n ||
					y > m || t[x][y] == '#')
				goto EndLoop;
			if (x == ex && y == ey) {
				++res;
				goto EndLoop;
			}
		}
		EndLoop: ;
		std::next_permutation(a, a + 4);
	}
	printf("%d", res);
	return 0;
}
} // namespace XSC062