JAVA进步一点点--数据结构与算法(广搜)--单词拆分

1368. 使网格图至少有一条有效路径的最小代价

JAVA进步一点点--数据结构与算法(广搜)--单词拆分
分析题意:类似于两个岛屿之间的距离,思路可以为把从根节点能到达的节点都保存到队列,然后花费1,把队列修改为队列中的节点可以到达的节点群(岛屿),如果岛屿已经包含了目标,则可以退出了
//1368. 使网格图至少有一条有效路径的最小代价
// 从题意可知,从00出发必然到达目标节点有两种情况
// (1)可以直接到达,则返回0
// (2)无法直接到达,则需要返回cost
// //当无法直接到达时,从根节点可以到达一些节点,然后对这些节点花费cost=1,则扩充了新节点的可到达的所有节点
// 此时形成一个递归性质的层序遍历,终止条件为到达目标值,剪枝条件为是否已经访问过

	public int minCost(int[][] grid) {
		boolean[][] visited = new boolean[grid.length][grid[0].length];
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[]{0, 0});
		int result = 0;
		outer:
		while (!queue.isEmpty()) {
			int size = queue.size();
			//对当前queue中的所有坐标作为起点进行dfs,查看能找到多少节点
			for (int i = 0; i < size; i++) {
				int[] cur = queue.poll();
				dfs(grid, visited, queue, cur[0], cur[1]);
				if (visited[grid.length - 1][grid[0].length - 1] == true) {
					break outer;
				}
			}
			//如果遍历之后还是没有发现,则需要对目前队列中的所有节点花费cost=1可以达到的点都加入到queue中
			int size2 = queue.size();
			for (int i = 0; i < size2; i++) {
				int[] cur = queue.poll();
				cost1(visited, queue, cur[0] + 1, cur[1]);
				cost1(visited, queue, cur[0] - 1, cur[1]);
				cost1(visited, queue, cur[0], cur[1] + 1);
				cost1(visited, queue, cur[0], cur[1] - 1);
			}
			result++;
		}
		return result;
	}

	public void dfs(int[][] grid, boolean[][] visited, Queue<int[]> queue, int row, int col) {
		if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || visited[row][col] == true) {
			return;
		}
		visited[row][col] = true;
		queue.add(new int[]{row, col});
		if (grid[row][col] == 1) {
			dfs(grid, visited, queue, row, col + 1);
		}
		if (grid[row][col] == 2) {
			dfs(grid, visited, queue, row, col - 1);
		}
		if (grid[row][col] == 3) {
			dfs(grid, visited, queue, row + 1, col);
		}
		if (grid[row][col] == 4) {
			dfs(grid, visited, queue, row - 1, col);
		}
	}

	public void cost1(boolean[][] visited, Queue<int[]> queue, int row, int col) {
		if (row < 0 || row >= visited.length || col < 0 || col >= visited[0].length || visited[row][col] == true) {
			return;
		}
		queue.add(new int[]{row, col});
	}

上一篇:LeetCode-778. 水位上升的泳池中游泳


下一篇:寒假刷题打卡第二十二 & 第二十三天 | 分治 & 搜索