【= 矩阵 =】

题目描述

传送门

解题思路

多源BFS🤣🤣🤣(看了题解)
1、找出所有为0的位置加入队列，不为0的置为-1
2、遍历队列，判断当前节点的上、下、左、右如果是-1则记为1同时入队列，0则距离为0不用重置
3、直至队列为空

解题方法

function updateMatrix($mat) {
   $queue = [];
   foreach($mat as $i => $vi) {
       foreach ($vi as $j => $vj) {
           if($mat[$i][$j] == 0) {
               $queue[] = [$i, $j];
           } else {
               $mat[$i][$j] = -1;
           }
       }
   }
   while(!empty($queue)) {
       $cur = array_shift($queue);
       $x = $cur[0];
       $y = $cur[1];
       // 上
       if(isset($mat[$x-1][$y]) && $mat[$x-1][$y] == -1) {
           $mat[$x-1][$y] = $mat[$x][$y]+1;
           $queue[] = [$x-1, $y];
       }
       if(isset($mat[$x+1][$y]) && $mat[$x+1][$y] == -1) {
           $mat[$x+1][$y] = $mat[$x][$y]+1;
           $queue[] = [$x+1, $y];
       }
       if(isset($mat[$x][$y-1]) && $mat[$x][$y-1] == -1) {
           $mat[$x][$y-1] = $mat[$x][$y]+1;
           $queue[] = [$x, $y-1];
       }
       if(isset($mat[$x][$y+1]) && $mat[$x][$y+1] == -1) {
           $mat[$x][$y+1] = $mat[$x][$y]+1;
           $queue[] = [$x, $y+1];
       }
   }
   return $mat;
}

在这里插入图片描述

// 还有优化空间，可将上下左右四个方向的判断直接按照[{-1,0},{1,0},{0,-1},{0,1}]直接遍历统一处理
// 代码会精简不少
func updateMatrix(mat [][]int) [][]int {
    queue := make([][]int, 0)
	for i := 0;i<len(mat);i++{
		for j:=0;j<len(mat[0]);j++{
			if mat[i][j] == 0 {
				queue = append(queue, []int{i,j})
			} else {
				mat[i][j] = -1
			}
		}
	}
	// direction := [][]int{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}
	for len(queue) != 0 {
		curr := queue[0]
		queue = queue[1:]
		x, y := curr[0], curr[1]
		if x-1 >= 0 && x-1 < len(mat) && mat[x-1][y] == -1 {
			mat[x-1][y] = mat[x][y] + 1
			queue = append(queue, []int{x - 1, y})
		}
		if x+1 >= 0 && x+1 < len(mat) && mat[x+1][y] == -1 {
			mat[x+1][y] = mat[x][y] + 1
			queue = append(queue, []int{x + 1, y})
		}
		if y-1 >= 0 && y-1 < len(mat[0]) && mat[x][y-1] == -1 {
			mat[x][y-1] = mat[x][y] + 1
			queue = append(queue, []int{x, y - 1})
		}
		if y+1 >= 0 && y+1 < len(mat[0]) && mat[x][y+1] == -1 {
			mat[x][y+1] = mat[x][y] + 1
			queue = append(queue, []int{x, y + 1})
		}
		
		// for _,v :range direction {
		// 	x,y := point[0]+v[0], point[0]+v[1]
		// 	if x>=0 && x <len(mat) && y>=0 && y<len(mat[0]) && mat[x][y] == -1 {
		// 		mat[x][y] = mat[point[0], point[1]]+1
		// 		queue = append(queue, []int{x,y})
		// 	}
		// }
	}
	return mat
}