{"id":"8c3a6f5d-4fa0-4847-9a10-67bf5d28ddd2","name":"As Far From Land As Possible","description":"Given an n*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.\r\n\r\nThe distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.\r\n","inputFormat":"First line contains an integer n.\r\nEach of next n lines contain n numbers containing either 0 or 1.","outputFormat":"Print a 2d matrix where each box contains distance to its nearest 0.","constraints":"1&lt;= n &lt;= 1000","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\ntypedef pair<int, int> pairs;\n\nint maxDistance(vector<vector<int>>&grid){\n // write code here\n \n \n}\n\nint main(){\n int n;\n cin>>n;\n \n vector<vector<int>>arr(n,vector<int>(n));\n for(int i=0;i<n;i++){\n for(int j=0;j<n;j++){\n int x;\n cin>>x;\n arr[i][j]=x;\n }\n }\n \n cout<<maxDistance(arr);\n}"},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.*;\n\npublic class Main {\n\n public static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n int n = Integer.parseInt(br.readLine());\n int[][] arr = new int[n][n];\n for (int i = 0; i < n; i++) {\n String[] st = br.readLine().split(\" \");\n for (int j = 0; j < n; j++) {\n arr[i][j] = Integer.parseInt(st[j]);\n }\n }\n\n System.out.println(maxDistance(arr));\n\n }\n public static class Pair{\n int row;\n int col;\n Pair(int row,int col)\n {\n this.row=row;\n this.col=col;\n }\n }\n\n public static int maxDistance(int[][] grid) {\n //write your code here\n\n}\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\n0 0 0\r\n0 1 1\r\n1 1 1\r\n","sampleOutput":"2\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"f1ec54c7-38c5-4b20-92e5-04f0328134ae","name":"As Far From Land As Possible","slug":"as-far-from-land-as-possible","type":1}],"next":{"id":"1b68f92c-4fb9-4950-af19-5c1c09b3e5d5","name":"As Far As From Land As Possible","type":0,"slug":"as-far-as-from-land-as-possible"},"prev":{"id":"130dfba4-627c-4dfb-b32c-4e200dab4854","name":"ROTTING ORANGES","type":3,"slug":"rotting-oranges"}}}

As Far From Land As Possible

Given an n*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|.

{"id":"8c3a6f5d-4fa0-4847-9a10-67bf5d28ddd2","name":"As Far From Land As Possible","description":"Given an n*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.\r\n\r\nThe distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.\r\n","inputFormat":"First line contains an integer n.\r\nEach of next n lines contain n numbers containing either 0 or 1.","outputFormat":"Print a 2d matrix where each box contains distance to its nearest 0.","constraints":"1&lt;= n &lt;= 1000","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\ntypedef pair<int, int> pairs;\n\nint maxDistance(vector<vector<int>>&grid){\n // write code here\n \n \n}\n\nint main(){\n int n;\n cin>>n;\n \n vector<vector<int>>arr(n,vector<int>(n));\n for(int i=0;i<n;i++){\n for(int j=0;j<n;j++){\n int x;\n cin>>x;\n arr[i][j]=x;\n }\n }\n \n cout<<maxDistance(arr);\n}"},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.*;\n\npublic class Main {\n\n public static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n int n = Integer.parseInt(br.readLine());\n int[][] arr = new int[n][n];\n for (int i = 0; i < n; i++) {\n String[] st = br.readLine().split(\" \");\n for (int j = 0; j < n; j++) {\n arr[i][j] = Integer.parseInt(st[j]);\n }\n }\n\n System.out.println(maxDistance(arr));\n\n }\n public static class Pair{\n int row;\n int col;\n Pair(int row,int col)\n {\n this.row=row;\n this.col=col;\n }\n }\n\n public static int maxDistance(int[][] grid) {\n //write your code here\n\n}\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\n0 0 0\r\n0 1 1\r\n1 1 1\r\n","sampleOutput":"2\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"f1ec54c7-38c5-4b20-92e5-04f0328134ae","name":"As Far From Land As Possible","slug":"as-far-from-land-as-possible","type":1}],"next":{"id":"1b68f92c-4fb9-4950-af19-5c1c09b3e5d5","name":"As Far As From Land As Possible","type":0,"slug":"as-far-as-from-land-as-possible"},"prev":{"id":"130dfba4-627c-4dfb-b32c-4e200dab4854","name":"ROTTING ORANGES","type":3,"slug":"rotting-oranges"}}}
plane

Editor

Loading...

As Far From Land As Possible

easy

Given an n*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|.

Constraints

1<= n <= 1000

Format

Input

First line contains an integer n. Each of next n lines contain n numbers containing either 0 or 1.

Output

Print a 2d matrix where each box contains distance to its nearest 0.

Example

Sample Input

3 0 0 0 0 1 1 1 1 1

Sample Output

2

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode