leetcode
leetcode 1851 ~ 1900
扫地机器人清扫过的空间个数

扫地机器人清扫过的空间个数

难度:

标签:

题目描述

代码结果

运行时间: 39 ms, 内存: 19.3 MB


/*
 * 题目思路:
 * 1. 使用Java Stream处理数据,模拟机器人移动并记录清扫的空间。
 * 2. 使用集合存储清扫过的空间,使用流操作来处理和过滤数据。
 */
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;

public class Solution {
    public int cleanedSpaces(int[][] room, int[] start) {
        Set<String> visited = new HashSet<>();
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[] position = {start[0], start[1]};
        int[] dirIndex = {0};
        visited.add(position[0] + "," + position[1]);

        IntStream.range(0, room.length * room[0].length).forEach(i -> {
            int newX = position[0] + directions[dirIndex[0]][0];
            int newY = position[1] + directions[dirIndex[0]][1];
            if (newX >= 0 && newX < room.length && newY >= 0 && newY < room[0].length && room[newX][newY] != 1 && !visited.contains(newX + "," + newY)) {
                position[0] = newX;
                position[1] = newY;
                visited.add(position[0] + "," + position[1]);
            } else {
                dirIndex[0] = (dirIndex[0] + 1) % 4;
            }
        });

        return visited.size();
    }
}

解释

方法:

这个题解利用模拟行走过程的方式来确定扫地机器人可以清扫的区域。它通过定义一个移动函数 move,根据当前方向和位置来决定下一步的动作。如果下一步的位置是可行走的(即为0),机器人就向该方向移动;否则,它就原地转向。整个过程中,机器人的位置和方向被记录在集合 vis 中以避免重复行动。同时,已清扫的位置被添加到另一个集合 ans 中。最后,函数返回 ans 集合的大小,即不重复的清扫过的格子数量。

时间复杂度:

O(m * n)

空间复杂度:

O(m * n)

代码细节讲解

🦆
在模拟行走过程中,`move` 函数是如何处理机器人遇到不可行进区域(即非0格子)的情况?
当机器人尝试移动到一个新位置时,`move` 函数首先会检查这个新位置是否有效,即位置是否在房间的边界内以及该位置是否为0(可行走区域)。如果这个新位置无法行走(比如是非0格子),则机器人不会移动到那个位置,而是保持在当前位置,并且函数会返回当前位置和新的方向,方向通过 `(tt + 1) % 4` 进行计算,表示机器人将顺时针转向下一个方向。
🦆
题解中提到,如果机器人无法向前行走就会原地转向,那么转向的具体规则是什么?是否总是顺时针转向下一个方向?
是的,转向规则是机器人会顺时针转向下一个方向。这是通过使用 `(tt + 1) % 4` 实现的,其中 `tt` 是当前方向的索引,通过对4取余数确保方向循环在四个可能的方向(向右、向下、向左、向上)之间。每次机器人遇到不可行进的区域时,都会应用这个规则进行转向。
🦆
题解中使用了两个集合 `vis` 和 `ans`,请问 `vis` 集合中存储的 `(x, y, tt)` 中的 `tt` 具体代表什么意思?
`tt` 在 `vis` 集合中的 `(x, y, tt)` 元组中代表机器人当前的方向。这个方向是整数索引,对应于机器人可能的四个移动方向(0代表向右,1代表向下,2代表向左,3代表向上)。存储方向是必要的,因为即使在相同的位置 `(x, y)`,不同的方向可能导致不同的后续行为,所以需要记录每一个位置和方向的组合以避免重复行为。
🦆
机器人清扫的过程中,`ans` 集合用于存储已清扫的格子,那么这个集合是否有可能重复记录某个格子?如果是,为什么?
`ans` 集合用来存储机器人已经清扫过的格子的坐标 `(x, y)`。理论上,由于 `ans` 是一个集合,它会自动处理重复的元素,即它不会存储重复的格子。然而,由于 `vis` 集合会阻止机器人重复进入相同位置和方向的状态,实际上机器人不会有机会多次清扫同一个格子。因此,在这种情况下,`ans` 中每个格子都只会被记录一次。

相关问题