龙空技术网

leetcode1091_go_二进制矩阵中的最短路径

每天都AC 69

前言:

目前咱们对“图中的一条路径长度为k”都比较关怀,你们都需要分析一些“图中的一条路径长度为k”的相关资讯。那么小编同时在网络上汇集了一些有关“图中的一条路径长度为k””的相关知识,希望看官们能喜欢,小伙伴们一起来学习一下吧!

题目

在一个 N × N 的方形网格中,每个单元格有两种状态:空(0)或者阻塞(1)。

一条从左上角到右下角、长度为 k 的畅通路径,由满足下述条件的单元格 C_1, C_2, ..., C_k 组成:

相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通(此时,C_i 和 C_{i+1} 不同且共享边或角)

C_1 位于 (0, 0)(即,值为 grid[0][0])

C_k 位于 (N-1, N-1)(即,值为 grid[N-1][N-1])

如果 C_i 位于 (r, c),则 grid[r][c] 为空(即,grid[r][c] == 0)

返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径,返回 -1 。

示例 1:输入:[[0,1],[1,0]] 输出:2

示例 2:输入:[[0,0,0],[1,1,0],[1,1,0]] 输出:4

提示:1 <= grid.length == grid[0].length <= 100

grid[i][j] 为 0 或 1

解题思路分析

1、广度优先搜索;时间复杂度O(n^2),空间复杂度O(n)

var dx = []int{-1, -1, -1, 0, 0, 1, 1, 1}var dy = []int{-1, 0, 1, -1, 1, -1, 0, 1}func shortestPathBinaryMatrix(grid [][]int) int {	if grid[0][0] == 1 {		return -1	}	n, m := len(grid), len(grid[0])	if grid[n-1][m-1] == 1 {		return -1	}	if n == 1 && m == 1 {		return 1	}	visited := make(map[[2]int]bool)	visited[[2]int{0, 0}] = true	queue := make([][3]int, 0)	queue = append(queue, [3]int{0, 0, 1})	for len(queue) > 0 {		node := queue[0]		queue = queue[1:]		x := node[0]		y := node[1]		v := node[2]		for i := 0; i < 8; i++ {			newX := x + dx[i]			newY := y + dy[i]			if 0 <= newX && newX < n && 0 <= newY && newY < m &&				grid[newX][newY] == 0 && visited[[2]int{newX, newY}] == false {				queue = append(queue, [3]int{newX, newY, v + 1})				visited[[2]int{newX, newY}] = true				if newX == n-1 && newY == m-1 {					return v + 1				}			}		}	}	return -1}

2、广度优先搜索;时间复杂度O(n^2),空间复杂度O(n)

var dx = []int{-1, -1, -1, 0, 0, 1, 1, 1}var dy = []int{-1, 0, 1, -1, 1, -1, 0, 1}func shortestPathBinaryMatrix(grid [][]int) int {	if grid[0][0] == 1 {		return -1	}	n, m := len(grid), len(grid[0])	if grid[n-1][m-1] == 1 {		return -1	}	if n == 1 && m == 1{		return 1	}	queue := make([]int, 0)	queue = append(queue, 0)	grid[0][0] = 1	for len(queue) > 0 {		node := queue[0]		queue = queue[1:]		x := node / m		y := node % m		for i := 0; i < 8; i++ {			newX := x + dx[i]			newY := y + dy[i]			if 0 <= newX && newX < n && 0 <= newY && newY < m && grid[newX][newY] == 0 {				queue = append(queue, newX*m+newY)				grid[newX][newY] = grid[x][y] + 1				if newX == n-1 && newY == m-1 {					return grid[n-1][m-1]				}			}		}	}	return -1}
总结

Medium题目,采用广度优先搜索解题

标签: #图中的一条路径长度为k