列表

详情

LCP 63. 弹珠游戏

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

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

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

注意：

示例 1：

输入： num = 4 plate = ["..E.",".EOW","..W."]

输出：[[2,1]]

解释： 在 [2,1] 处打入弹珠，弹珠前进 1 步后遇到转向器，前进方向顺时针旋转 90 度，再前进 1 步进入洞中。 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{:width="350px"}

示例 3：

输入： num = 3 plate = [".....","....O","....O","....."]

输出：[]

解释： 由于弹珠被击中后只能前进 3 步，且不能在弹珠洞和弹珠盘四角打入弹珠，故不存在能让弹珠入洞的打入位置。

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<vector<int>> ballGame(int num, vector<string>& plate) { } };

java 解法, 执行用时: 21 ms, 内存消耗: 53.7 MB, 提交时间: 2023-10-25 07:44:32 

class Solution {

    int[][] dirs={{-1,0},{0,1},{1,0},{0,-1}};
    int n,m;
    char[][] g;
    public int[][] ballGame(int num, String[] plate) {
        n=plate.length;
        m=plate[0].length();
        g=new char[n][m];

        for(int i=0;i<n;i++){
            g[i]=plate[i].toCharArray();
        }

        List<Pair<Integer,Integer>> list=new ArrayList<>();

        //上边
        for(int j=1;j<m-1;j++){
            if(g[0][j]=='.'){
                //只有在空白处才能打弹珠
                if(help(0,j,num,2)){
                    list.add(new Pair<Integer,Integer>(0,j));
                }
            }
        }

        // System.out.println(list.size());

        //下边
        for(int j=1;j<m-1;j++){
            if(g[n-1][j]=='.'){
                //只有在空白处才能打弹珠
                if(help(n-1,j,num,0)){
                    list.add(new Pair<Integer,Integer>(n-1,j));
                }
            }
        }

        // System.out.println(list.size());

        //左边
        for(int i=1;i<n-1;i++){
            if(g[i][0]=='.'){
                //只有在空白处才能打弹珠
                if(help(i,0,num,1)){
                    list.add(new Pair<Integer,Integer>(i,0));
                }
            }
        }

        // System.out.println(list.size());

        //右边
        for(int i=1;i<n-1;i++){
            if(g[i][m-1]=='.'){
                //只有在空白处才能打弹珠
                if(help(i,m-1,num,3)){
                    list.add(new Pair<Integer,Integer>(i,m-1));
                }
            }
        }
        // (2n+2m) * Math.min((n*m),num)    1000 * 1000 *1000
        // System.out.println(list.size());

        int[][] ans=new int[list.size()][2];
        for(int i=0;i<list.size();i++){
            ans[i][0]=list.get(i).getKey();
            ans[i][1]=list.get(i).getValue();
        }

        return ans;
    }

    boolean help(int x,int y,int step,int d){

        while(step--!=0){

            x+=dirs[d][0];
            y+=dirs[d][1];

            //出界
            if(x<0||x>=n||y<0||y>=m)    return false;

            //弹珠洞
            if(g[x][y]=='O')    return true;

            //转向器
            if(g[x][y]=='E'){
                d=(d+1)%4;
            }else if(g[x][y]=='W'){
                d=(d-1+4)%4;
            }

        }

        //不能在num步内入洞
        return false;
    }

}

cpp 解法, 执行用时: 164 ms, 内存消耗: 37.3 MB, 提交时间: 2023-10-25 07:44:15 

class Solution {
public:
    vector<vector<int>> dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    vector<vector<int>> ballGame(int num, vector<string>& plate) {
        int m = plate.size();
        int n = plate[0].size();

        auto check = [&](int x, int y, int d) -> bool{
            int left = num;
            while(plate[x][y] != 'O'){
                if(left == 0)
                    return false;
                if(plate[x][y] == 'W')
                    d = (d+3)%4;
                else if(plate[x][y] == 'E')
                    d = (d+1)%4;
                x += dirs[d][0];
                y += dirs[d][1];
                if(x<0 || x>=m || y<0 || y>=n)
                    return false;
                left -= 1;
            }
            return true;
        };

        vector<vector<int>> ans;
        for(int i=1; i<m-1; ++i){
            if(plate[i][0] == '.' && check(i, 0, 0))      //左边
                ans.push_back({i,0});
            if(plate[i][n-1] == '.' && check(i, n-1, 2))  //右边
                ans.push_back({i,n-1});
        }
        for(int i=1; i<n-1; ++i){
            if(plate[0][i] == '.' && check(0, i, 1))      //上边
                ans.push_back({0,i});
            if(plate[m-1][i] == '.' && check(m-1, i, 3))  //下边
                ans.push_back({m-1, i});
        }
        return ans;
    }
};

cpp 解法, 执行用时: 1560 ms, 内存消耗: 67 MB, 提交时间: 2023-10-25 07:43:45 

class Solution {
    static const int MAXN = 1000;

    int n, m;
    // 按上右下左的顺序存储方向，方便旋转
    short dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};

    // 把小球的坐标和方向压缩成 int
    int gao(int i, int j, int k) {
        return i * m * 4 + j * 4 + k;
    }

    // 把 int 解压成坐标和方向
    void ungao(int p, int &i ,int &j ,int &k) {
        i = p / (m * 4);
        j = p / 4 % m;
        k = p % 4;
    }

public:
    vector<vector<int>> ballGame(int num, vector<string>& plate) {
        n = plate.size(); m = plate[0].size();
        static int dis[MAXN][MAXN][4];
        for (int i = 0;i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < 4; k++) dis[i][j][k] = -1;

        static int q[MAXN * MAXN * 4 + 10];
        int head = 0, tail = 0;
        // 从 O 开始搜索
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (plate[i][j] == 'O')
            for (int k = 0; k < 4; k++) q[tail++] = gao(i, j, k), dis[i][j][k] = 0;
        while (head < tail) {
            int p = q[head++];
            int i, j, k; ungao(p, i, j, k);
            // 往当前方向移动一步
            int ii = i + dir[k][0], jj = j + dir[k][1], kk = k;
            // 小球掉出棋盘
            if (ii < 0 || jj < 0 || ii >= n || jj >= m) continue;
            // 遇到 W，因为是倒过来搜索所以要顺时针旋转
            if (plate[ii][jj] == 'W') kk = (kk + 1) % 4;
            // 遇到 E，因为是倒过来搜索所以要逆时针旋转
            else if (plate[ii][jj] == 'E') kk = (kk + 3) % 4;
            if (dis[ii][jj][kk] >= 0) continue;
            q[tail++] = gao(ii, jj, kk);
            dis[ii][jj][kk] = dis[i][j][k] + 1;
        }
        
        // 统计答案，注意题目要求只能从边缘的 . 格子进入，而且方向还要垂直于边缘
        vector<vector<int>> ans;
        for (int i = 1; i + 1 < n; i++) if (plate[i][0] == '.' && dis[i][0][3] >= 0 && dis[i][0][3] <= num) ans.push_back({i, 0});
        for (int i = 1; i + 1 < n; i++) if (plate[i][m - 1] == '.' && dis[i][m - 1][1] >= 0 && dis[i][m - 1][1] <= num) ans.push_back({i, m - 1});
        for (int j = 1; j + 1 < m; j++) if (plate[0][j] == '.' && dis[0][j][0] >= 0 && dis[0][j][0] <= num) ans.push_back({0, j});
        for (int j = 1; j + 1 < m; j++) if (plate[n - 1][j] == '.' && dis[n - 1][j][2] >= 0 && dis[n - 1][j][2] <= num) ans.push_back({n - 1, j});
        return ans;
    }
};

golang 解法, 执行用时: 48 ms, 内存消耗: 8.3 MB, 提交时间: 2023-10-25 07:43:12 

var dirs = []struct{ x, y int }{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 右下左上（顺时针）

func ballGame(num int, plate []string) (ans [][]int) {
	m, n := len(plate), len(plate[0])
	check := func(x, y, d int) bool {
		for left := num; plate[x][y] != 'O'; left-- {
			if left == 0 { // 无剩余步数
				return false
			}
			if plate[x][y] == 'W' { // 逆时针
				d = (d + 3) % 4
			} else if plate[x][y] == 'E' { // 顺时针
				d = (d + 1) % 4
			}
			x += dirs[d].x
			y += dirs[d].y
			if x < 0 || x >= m || y < 0 || y >= n { // 从另一边出去了
				return false
			}
		}
		return true
	}
	for j := 1; j < n-1; j++ {
		if plate[0][j] == '.' && check(0, j, 1) {
			ans = append(ans, []int{0, j})
		}
		if plate[m-1][j] == '.' && check(m-1, j, 3) {
			ans = append(ans, []int{m - 1, j})
		}
	}
	for i := 1; i < m-1; i++ {
		if plate[i][0] == '.' && check(i, 0, 0) {
			ans = append(ans, []int{i, 0})
		}
		if plate[i][n-1] == '.' && check(i, n-1, 2) {
			ans = append(ans, []int{i, n - 1})
		}
	}
	return
}

python3 解法, 执行用时: 112 ms, 内存消耗: 22.6 MB, 提交时间: 2023-10-25 07:42:52 

DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）

class Solution:
    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:
        m, n = len(plate), len(plate[0])

        def check(x: int, y: int, d: int) -> bool:
            left = num
            while plate[x][y] != 'O':
                if left == 0: return False  # 无剩余步数
                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针
                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针
                x += DIRS[d][0]
                y += DIRS[d][1]
                if not (0 <= x < m and 0 <= y < n): return False  # 出界
                left -= 1
            return True

        ans = []
        for j in range(1, n - 1):
            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边
            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边
        for i in range(1, m - 1):
            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边
            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边
        return ans

上一题

© 2024 leetcode.cn