华为OD机试真题- 机器人活动区域

题目描述:

现有一个机器人,可放置于 M × N 的网格中任意位置,每个网格包含一个非负整数编号。当相邻网格的数字编号差值的绝对值小于等于 1 时,机器人可在网格间移动

问题:求机器人可活动的最大范围对应的网格点数目。

说明:

1)网格左上角坐标为 (0, 0),右下角坐标为 (m-1, n-1)

2)机器人只能在相邻网格间上、下、左、右移动

示例1

输入

4 4
1 2 5 2
2 4 4 5
3 5 7 1
4 6 2 4

alt

输出:

6

说明:图中绿色区域,相邻网格差值绝对值都小于等于1,且为最大区域,对应网格点数目为6

示例2

输入

2 3 1 3 5 4 1 3

输出:

1

说明:任意两个相邻网格的差值绝对值都大于1,机器人不能在网格间移动,只能在单个网格内活动,对应网格点数目为 1

题解

这道题目本质上是一个图的连通性问题。

可以将网格看作一个图,每个格子是一个节点,相邻且差值不超过 1 的格子之间有一条边。问题就转化为找到最大的连通分量。

解决这个问题的一个有效方法是使用深度优先搜索(DFS)或广度优先搜索(BFS)或者 并查集(DSU)。

这里以 DFS 为例来解释解题思路:

遍历整个网格,对每个未访问的格子进行 DFS。

在 DFS 过程中,检查当前格子的上下左右四个相邻格子。

如果相邻格子未访问过,且与当前格子的差值绝对值不超过 1,则继续对该相邻格子进行 DFS。

实现时,可以使用一个二维数组来存储网格数据,另一个二维数组来标记已访问的格子。

源码

public class RobotLiveArea {

	static Input input ;
	static {
		input = new Input("4 4\n" +
				"1 2 5 2\n" +
				"2 4 4 5\n" +
				"3 5 7 1\n" +
				"4 6 2 4");
	}
	static  int[][] area;
	static int m, n;
	static boolean[][] visited;

	public static void main(String[] args) {
		String[] str = input.nextLine().split(" ");

		m = Integer.parseInt(str[0]);
		n = Integer.parseInt(str[1]);
		area = new int[m][n];
		visited = new boolean[m][n];

		for (int i = 0; i < m; i++) {
			String[] ss = input.nextLine().split(" ");
			for (int j = 0; j < n; j++) {
				area[i][j] = Integer.parseInt(ss[j]);
			}
		}

		int result = 1;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				result = Math.max(dfs(i, j), result);
			}
		}

		System.out.println(result);
	}

	public static int dfs(int x, int y) {
		if (isOverBound(x, y)) {
			return 0;
		}
		if (visited[x][y]) {
			return 0;
		}
		visited[x][y] = true;

		int result = 1;
		int[][] direction = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
		for (int i = 0; i < direction.length; i++) {
			int newX = x + direction[i][0];
			int newY = y + direction[i][1];
			if (!isOverBound(newX, newY) // 下一个坐标没有越界
					&& !visited[newX][newY]  // 下一个坐标没有被访问过
					&& Math.abs(area[newX][newY] - area[x][y]) <= 1) { // 下一个高度差不是过大
				result += dfs(newX, newY);
			}
		}
		return result;
	}

	public static boolean isOverBound(int x, int y) {
		if (x >= m || y >= n || x < 0 || y < 0) {
			return true;
		}
		return false;
	}

}
#国央企求职进展汇总#
全部评论

相关推荐

缓存穿透是指当一个请求查询/访问一个不存在于缓存中的数据时,该请求会穿透缓存层,直接访问后端数据库或其他数据存储系统。这可能导致对后端系统的过度负载,并且每个请求都需要从后端获取数据,无法利用缓存提供的性能优势。在前端防止缓存穿透问题的常见方法包括:https://www.nowcoder.com/issue/tutorial?zhuanlanId=Mg58Em&amp;amp;uuid=5f0bf65b3be04ac8a2beb28f857943a6输入合法性验证:在接收到请求之前,对请求的输入进行合法性验证。例如,对于用户输入的查询参数或请求的标识符,进行验证并确保其符合预期的格式和范围。如果请求的数据不存在或无效,可以提前进行处理,返回适当的响应,而不是单纯地将请求传递到后端。布隆过滤器(Bloom&nbsp;Filter):布隆过滤器是一种概率型数据结构,用于快速判断一个元素是否存在于集合中。在进行查询之前,可以使用布隆过滤器对缓存键进行检查,以过滤掉在缓存中一定不存在的键。这样可以减少对后端系统的不必要查询,同时提高缓存的命中率。缓存空值(Cache&nbsp;Miss):对于请求中查询的数据,即使在后端不存在该数据,也在缓存中存储一个空值作为响应。这样,在下次查询时,可以直接从缓存中获取空值作为响应,而不需要再次查询后端系统。这种方式可以减少对后端系统的请求次数,并加快响应速度。设置热门数据的预热策略:对于一些热门的数据或常用的查询,可以在系统启动或低峰期预先将其加载到缓存中。这样可以确保这部分数据在真正被请求时已经存在于缓存中,减少缓存穿透的可能性。使用缓存层/中间件:引入缓存层或中间件作为前端和后端之间的代理,用于处理查询请求和缓存的查询结果。缓存层可以缓存不同类型的数据,并根据缓存策略和配置决定是否向后端查询数据。这样可以集中管理缓存逻辑,并提供更高效的数据访问。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务