package LeetCode_1162
import java.util.*
/**
* 1162. As Far from Land as Possible
* https://leetcode.com/problems/as-far-from-land-as-possible/
* Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land,
* find a water cell such that its distance to the nearest land cell is maximized, and return the distance.
* If no land or water exists in the grid, return -1.
The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.
Example 1:
Input: grid = [
[1,0,1],
[0,0,0],
[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.
* */
class Solution {
/*
* solution: BFS, save all land in queue then start bfs to increasing the distance for each position,
* Time complexity:O(mn), Space complexity:O(mn)
* */
fun maxDistance(grid: Array<IntArray>): Int {
if (grid == null || grid.isEmpty()) {
return -1
}
var result = 0
val m = grid.size
val n = grid[0].size
val queue = LinkedList<Pair<Int, Int>>()
val visited = Array(m) { BooleanArray(n) }
val directions = intArrayOf(0, 1, 0, -1, 0)
for (i in 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == 1) {
//put the location of land in queue
visited[i][j] = true
queue.offer(Pair(i, j))
}
}
}
while (queue.isNotEmpty()) {
val size = queue.size
for (i in 0 until size) {
val cur = queue.poll()
val x = cur.first
val y = cur.second
for (d in 0 until 4) {
val newX = x + directions[d]
val newY = y + directions[d + 1]
if (newX < 0 || newX >= m || newY < 0 || newY >= n || visited[newX][newY]) {
continue
}
visited[newX][newY] = true
//update the new distance
grid[newX][newY] = grid[x][y] + 1
result = Math.max(result, grid[newX][newY])
queue.offer(Pair(newX, newY))
}
}
}
//-1 is for do one more useless loop in bfs
return result - 1
}
}