“O” 表示弹珠洞（弹珠到达后会落入洞中，并停止前进）；

来源：网络整理更新时间：2024-09-04 01:02:40 点击：

在这里插入图片描述

每日算法 - JavaScript解析：弹珠游戏

一、任务描述：

欢迎各位来到「力扣嘉年华」，接下来将为各位介绍在活动中广受好评的弹珠游戏。

N*M 大小的弹珠盘的初始状态信息记录于一维字符串型数组 plate 中，数组中的每个元素为仅由 “O”、“W”、“E”、“.” 组成的字符串。其中：

游戏规则要求仅能在边缘位置的空白区域处（弹珠盘的四角除外）沿与边缘垂直的方向打入弹珠，并且打入后的每颗弹珠最多能前进 num 步。请返回符合上述要求且可以使弹珠最终入洞的所有打入位置。

注意

你可以按任意顺序返回答案。若弹珠已到达弹珠盘边缘并且仍沿着出界方向继续前进，则将直接出界。

本题取自 leetcode 秋赛题集

》示例一：

输入： 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 步后进入洞中。

效果如下图所示：

在这里插入图片描述

二、题意解析

示例图

地形解析如下：

根据题目，可以思考得出以下条件和限制：

根据示例可以把传入的 plate 理解成一个倒置的直角坐标轴，也就是一个平面。该地图上，存在 4 种类型的地形，不同地形带来的效果不同。

弹珠的初始位置规定，只能在地图的边缘空白区域 " . " 发射且不能为地图的四个角，以上面的图片为例，初始点为如上蓝色框框的区域。

弹珠走向判定，这个是这道算法题的一个小难点。根据题目，我们可以知道地形对弹珠的影响是以顺/逆时针为判定的，所以，我们需要对方向进行顺序排列且对不同方向前进时，Y和X坐标的加减情况进行枚举。如下图所示：

在这里插入图片描述

解题思路①

根据题目可知，由于路径是唯一的，一个入口只会对应一个唯一的出口；一个入口+弹珠进入出口的方向由坐标固定的，可以找到唯一的入口。

因此，指需要筛选出，所有符合规定的出发点，按照指定的弹珠移动逻辑。模拟弹珠行走，即可计算出成功进洞弹珠的入口。

具体逻辑和条件规则，上面也详细讲解了。主要是弹珠移动方向和对应地形造成移动方向变更的问题。

三、解决方案：

该解决方案仅供参考，并非最优解。可以自行发掘，理解算法思维最重要！

/**
 * @param {number} num
 * @param {string[]} plate
 * @return {number[][]}
 */
var ballGame = function(num, plate) {
    // 地图数组
    let _map = plate.map(item => item.split(''))
    // 弹珠位置
    let marbles_Y = Infinity
    let marbles_X = Infinity
    // 地图边界
    let Y_Len = _map.length -1
    let X_Len = _map[0].length -1
    let successInitPoint = []
    let direction = null
    // 对应顺时针： 上右下左的YX加减情况
    let directionEnum = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    for(let Y = 0; Y < Y_Len + 1; Y++) {
        for(let X = 0; X < X_Len + 1; X++) {
            // 限定初始点位置
            if(
                _map[Y][X] == '.' &&
                (Y == 0 || X == 0 || Y == Y_Len || X == X_Len) &&
                [Y, X].toString() != [0, 0].toString() &&
                [Y, X].toString() != [Y_Len, 0].toString() &&
                [Y, X].toString() != [0, X_Len].toString() &&
                [Y, X].toString() != [Y_Len, X_Len].toString()
            ) {
                // 定义弹珠位置
                marbles_Y = Number(Y)
                marbles_X = Number(X)
                // 定义初始方向
                if(Y == 0) direction = 2
                else if(Y == (Y_Len)) direction = 0
                else if(X == 0) direction = 1
                else if(X == (X_Len)) direction = 3
                // 定义步数
                let steps = num
                while(_map[marbles_Y][marbles_X] !== 'O') {
                    if(steps === 0) break
                    
                    // 限定踩到 EW 的逻辑
                    // E为顺时针90度，对应上面定义的枚举值，为索引+1且不能超出索引，故取余数
                    if(_map[marbles_Y][marbles_X] == 'E') direction =  (direction + 1) % 4
                    // W为逆时针90度，对应上面定义的枚举值， 相当于走完一圈再-1（4-1=3），为索引+3且不能超出索引，故取余数
                    else if(_map[marbles_Y][marbles_X] == 'W') direction =  (direction + 3) % 4
                    // 根据上面枚举的方向加减值
                    marbles_Y += Number(directionEnum[direction][0])
                    marbles_X += Number(directionEnum[direction][1])
                    // 判断是否超出边界
                    if(marbles_Y < 0 || marbles_Y > Y_Len || marbles_X < 0 || marbles_X > X_Len) break
                    // 判断结束时， 该弹珠是否成功进洞或者超出边界
                    else if(_map[marbles_Y][marbles_X] === 'O') {
                        successInitPoint.push([Y, X])
                        break
                    }
                    steps -= 1
                }
            } else continue
        }
    }
    // console.log(_map)
    return successInitPoint
};