题目描述
欢迎各位来到「力扣嘉年华」,接下来将为各位介绍在活动中广受好评的弹珠游戏。
N*M
大小的弹珠盘的初始状态信息记录于一维字符串型数组 plate
中,数组中的每个元素为仅由 "O"
、"W"
、"E"
、"."
组成的字符串。其中:
"O"
表示弹珠洞(弹珠到达后会落入洞中,并停止前进);"W"
表示逆时针转向器(弹珠经过时方向将逆时针旋转 90 度);"E"
表示顺时针转向器(弹珠经过时方向将顺时针旋转 90 度);"."
表示空白区域(弹珠可通行)。
游戏规则要求仅能在边缘位置的 空白区域 处(弹珠盘的四角除外)沿 与边缘垂直 的方向打入弹珠,并且打入后的每颗弹珠最多能 前进 num
步。请返回符合上述要求且可以使弹珠最终入洞的所有打入位置。你可以 按任意顺序 返回答案。
注意:
- 若弹珠已到达弹珠盘边缘并且仍沿着出界方向继续前进,则将直接出界。
样例
输入:
num = 4
plate = ["..E.",".EOW","..W."]
输出:[[2,1]]
解释:
在 [2,1] 处打入弹珠,弹珠前进 1 步后遇到转向器,前进方向顺时针旋转 90 度,再前进 1 步进入洞中。
输入:
num = 5
plate = [".....","..E..",".WO..","....."]
输出:[[0,1],[1,0],[2,4],[3,2]]
解释:
在 [0,1] 处打入弹珠,弹珠前进 2 步,遇到转向器后前进方向逆时针旋转 90 度,再前进 1 步进入洞中。
在 [1,0] 处打入弹珠,弹珠前进 2 步,遇到转向器后前进方向顺时针旋转 90 度,再前进 1 步进入洞中。
在 [2,4] 处打入弹珠,弹珠前进 2 步后进入洞中。
在 [3,2] 处打入弹珠,弹珠前进 1 步后进入洞中。
输入:
num = 3
plate = [".....","....O","....O","....."]
输出:[]
解释:
由于弹珠被击中后只能前进 3 步,且不能在弹珠洞和弹珠盘四角打入弹珠,故不存在能让弹珠入洞的打入位置。
限制
1 <= num <= 10^6
1 <= plate.length, plate[i].length <= 1000
plate[i][j]
仅包含"O"
、"W"
、"E"
、"."
。
算法1
(暴力枚举) $O((m + n)num)$
- 直接从每个合法的起点暴力判断是否可以达到合法终点,由于路径是固定的,所以可以直接递归判断是否合法。
时间复杂度
- 共有 $O(m + n)$ 个合法位置,每次判断需要 $O(num)$ 的时间,故总时间复杂度为 $O((m + n)num)$。
空间复杂度
- 需要 $O(m + n + num)$ 的额外空间存储系统栈和答案。
C++ 代码
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
class Solution {
private:
int m, n;
bool find(int x, int y, int d, int num, const vector<string> &plate) {
if (num < 0)
return false;
if (x < 0 || x >= m || y < 0 || y >= n)
return false;
if (plate[x][y] == 'O')
return true;
if (plate[x][y] == 'E')
d = (d + 1) % 4;
else if (plate[x][y] == 'W')
d = (d + 3) % 4;
return find(x + dx[d], y + dy[d], d, num - 1, plate);
}
public:
vector<vector<int>> ballGame(int num, vector<string>& plate) {
m = plate.size(); n = plate[0].size();
vector<vector<int>> ans;
for (int y = 1; y < n - 1; y++) {
if (plate[0][y] == '.' && find(0, y, 0, num, plate))
ans.push_back({0, y});
if (plate[m - 1][y] == '.' && find(m - 1, y, 2, num, plate))
ans.push_back({m - 1, y});
}
for (int x = 1; x < m - 1; x++) {
if (plate[x][0] == '.' && find(x, 0, 3, num, plate))
ans.push_back({x, 0});
if (plate[x][n - 1] == '.' && find(x, n - 1, 1, num, plate))
ans.push_back({x, n - 1});
}
return ans;
}
};
算法2
(宽度优先遍历) $O(mn)$
- 每个终点的四个方向作为起始点,开始宽度优先遍历,找到可以在 $num$ 之内到达的起始点。
- 由于 Leetcode 的错误数据配置,此正解算法暂时会被卡常数超时。
时间复杂度
- 每个位置和方向最多遍历一次,故时间复杂度为 $O(mn)$。
空间复杂度
- 需要 $O(mn)$ 的额外空间存储距离数组和队列。
C++ 代码
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int N = 1000;
class Solution {
private:
int dis[N][N][4], q[N * N * 4][3], h, t;
public:
vector<vector<int>> ballGame(int num, vector<string>& plate) {
const int m = plate.size(), n = plate[0].size();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < 4; k++)
dis[i][j][k] = -1;
h = t = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (plate[i][j] == 'O')
for (int k = 0; k < 4; k++) {
dis[i][j][k] = 0;
q[t][0] = i; q[t][1] = j; q[t][2] = k; t++;
}
vector<vector<int>> ans;
while (h < t) {
int x = q[h][0], y = q[h][1], d = q[h][2];
h++;
int tx = x + dx[d], ty = y + dy[d], td = d;
if (tx < 0 || tx >= m || ty < 0 || ty >= n)
continue;
if (plate[tx][ty] == 'O')
continue;
if (plate[tx][ty] == 'E')
td = (td + 3) % 4;
else if (plate[tx][ty] == 'W')
td = (td + 1) % 4;
if (dis[tx][ty][td] != -1)
continue;
if (dis[x][y][d] >= num)
continue;
dis[tx][ty][td] = dis[x][y][d] + 1;
q[t][0] = tx; q[t][1] = ty; q[t][2] = td; t++;
}
for (int y = 1; y < n - 1; y++) {
if (plate[0][y] == '.' && dis[0][y][0] != -1)
ans.push_back({0, y});
if (plate[m - 1][y] == '.' && dis[m - 1][y][2] != -1)
ans.push_back({m - 1, y});
}
for (int x = 1; x < m - 1; x++) {
if (plate[x][0] == '.' && dis[x][0][3] != -1)
ans.push_back({x, 0});
if (plate[x][n - 1] == '.' && dis[x][n - 1][1] != -1)
ans.push_back({x, n - 1});
}
return ans;
}
};