LCP 63-弹珠游戏

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 11:24:24 2023-09-13 11:24:24 Updated    

欢迎各位来到「力扣嘉年华」，接下来将为各位介绍在活动中广受好评的弹珠游戏。 N*M 大小的弹珠盘的初始状态信息记录于一维字符串型数组 plate
中，数组中的每个元素为仅由 "O"、"W"、"E"、"." 组成的字符串。其中： - "O"
表示弹珠洞（弹珠到达后会落入洞中，并停止前进）； - "W" 表示逆时针转向器（弹珠经过时方向将逆时针旋转 90 度）； - "E"
表示顺时针转向器（弹珠经过时方向将顺时针旋转 90 度）； - "." 表示空白区域（弹珠可通行）。 游戏规则要求仅能在边缘位置的 空白区域
处（弹珠盘的四角除外）沿 与边缘垂直 的方向打入弹珠，并且打入后的每颗弹珠最多能 前进 num
步。请返回符合上述要求且可以使弹珠最终入洞的所有打入位置。你可以 按任意顺序 返回答案。 注意： -
若弹珠已到达弹珠盘边缘并且仍沿着出界方向继续前进，则将直接出界。 示例 1： > 输入： >num = 4 >plate = ["..E.",".EOW","..W."] > > 输出：[[2,1]] > > 解释： > 在 [2,1] 处打入弹珠，弹珠前进 1
步后遇到转向器，前进方向顺时针旋转 90 度，再前进 1 步进入洞中。
![b054955158a99167b8d51da0e22a54da.gif](https://pic.leetcode-
cn.com/1630392649-BoQncz-b054955158a99167b8d51da0e22a54da.gif){:width=”300px”}
示例 2： > 输入： >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
步后进入洞中。 ![b44e9963239ae368badf3d00b7563087.gif](https://pic.leetcode-
cn.com/1630392625-rckbdy-b44e9963239ae368badf3d00b7563087.gif){:width=”350px”}
示例 3： > 输入： >num = 3 >plate = [".....","....O","....O","....."] > >
输出：[] > > 解释： > 由于弹珠被击中后只能前进 3 步，且不能在弹珠洞和弹珠盘四角打入弹珠，故不存在能让弹珠入洞的打入位置。 提示：
- 1 <= num <= 10^6 - 1 <= plate.length, plate[i].length <= 1000 -
plate[i][j] 仅包含 "O"、"W"、"E"、"."

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    List<int[]> list = new ArrayList<>();
    public int[][] ballGame(int num, String[] plate) {
        int n = plate.length, m = plate[0].length();
        int dir = 0;
        //    0     模拟四个方向
        // 3     1
        //    2  
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if ((i == 0 || j == 0 || i == n-1 || j == m-1) && plate[i].charAt(j) == '.') {
                    if ( !((i == 0 && j == 0) || (i == 0 && j == m-1) 
                        || (j == 0 && i == n-1) || (i == n-1 && j == m-1))) { 
                        if (i == 0) 
                            dir = 0;
                        else if (i == n-1) 
                            dir = 2;
                        else if (j == 0) 
                            dir = 3;
                        else 
                            dir = 1;
                        if (dfs(i, j, plate, num, n, m, dir)) { 
                           list.add(new int[]{i,j});
                        }
                    }
                }
            }
        } 
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i); 
        }
        return res;
    }
    private boolean dfs(int x, int y, String[] plate, int num, int n, int m, int dir) {          
        if (x >= n || x < 0 || y >= m || y < 0 || num < 0) 
            return false;
        num--;
        if (plate[x].charAt(y) == 'O') {
            return true;
        } else if (plate[x].charAt(y) == 'E') {
            dir++;
            if (dir > 3) 
                dir = 0;
        } else if (plate[x].charAt(y) == 'W') {
            dir--;
            if (dir < 0) 
                dir = 3;
        } 
        if (dir == 0) {
            x++;
        } else if (dir == 1) {
            y--;
        } else if (dir == 2) {
            x--;
        } else if (dir == 3) {
            y++;
        }
        return  dfs(x, y, plate, num, n, m, dir);
    }
}
 Comments
On this page
LCP 63-弹珠游戏