[LeetCode] 935. Knight Dialer

2024-09-06 04:58

文章标签 leetcode knight 935 dialer

本文主要是介绍[LeetCode] 935. Knight Dialer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/shortest-bridge/description/

题目

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

Input: [[0,1],[1,0]]
Output: 1

Example 2:

Input: [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Note:

1 <= A.length = A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1

题目大意

给定二维数组A中，有两个岛（每个岛由1组成，被0保卫）

现在，我们将0变为1，以使两岛连接起来，成为一个岛。

求翻转 0 的最小数目。

思路

首先，选一个岛，然后dfs膨胀，将该岛的1变为-1。将岛的每个坐标放入队列queue中。用queue 进行 bfs ，若元素为0，那么继续放入queue 遍历，放入queue的点都置为-1；若元素为1，则已遍历到另个岛。

class Solution {int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};Queue<int[]> queue = new LinkedList<>();public void dfsf(int[][] A,int r,int l,int rlen,int llen){if(!(r>=0 && r<rlen && l>=0 && l<llen && A[r][l]==1) )return;A[r][l] = -1;queue.offer(new int[]{r,l});for(int [] direction:directions){dfsf(A,r+direction[0],l+direction[1],rlen,llen);}}public int shortestBridge(int[][] A) {boolean flag = true;for (int i = 0; i < A.length && flag; i++)for (int j = 0; j < A[0].length && flag; j++)if (A[i][j] == 1) {dfsf(A, i,j ,A.length,A[0].length);flag = false;break;}int level = 0;while(!queue.isEmpty()){int queueSize = queue.size();level++;while (queueSize-->0){int[] cur = queue.poll();for(int [] direction:directions){int tr = cur[0] + direction[0];int tl = cur[1] + direction[1];if(!(tr>=0 && tr<A.length && tl>=0 && tl< A[0].length))continue;if(A[tr][tl]==1)return level-1;else if(A[tr][tl]==0){queue.offer(new int[]{tr,tl});A[tr][tl] = -1;}}}}return -1;}
}