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
    }
}