{"id":"3719b0f4-558c-41ce-bd5a-ddd7bbd55a9a","name":"Zero One Matrix","description":"Given an m*n binary matrix mat, return the distance of the nearest 0 for each cell.\r\n\r\nThe distance between two adjacent cells is 1.","inputFormat":"First line contains two integers n and m.\r\nEach of next n lines contain m 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\r\n1&lt;= e &lt;= n*(n-1)/2","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<vector<int>> updateMatrix(vector<vector<int>>& matrix){\n // write your code here\n}\n\nint main(){\n \n int n,m;\n cin>>n>>m;\n \n vector<vector<int>>arr(n,vector<int>(m));\n for(int i=0;i<n;i++){\n for(int j=0;j<m;j++){\n int x;\n cin>>x;\n arr[i][j]=x;\n }\n }\n \n vector<vector<int>>ans=updateMatrix(arr);\n \n for(int i=0;i<n;i++){\n for(int j=0;j<m;j++){\n cout<<ans[i][j]<<\" \";\n }\n cout<<endl;\n }\n}"},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.*;\n\nclass Main {\n public static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n String[] st = br.readLine().split(\" \");\n int n = Integer.parseInt(st[0]);\n int m = Integer.parseInt(st[1]);\n\n int[][] arr = new int[n][m];\n\n for (int i = 0; i < n; i++) {\n st = br.readLine().split(\" \");\n for (int j = 0; j < m; j++) {\n arr[i][j] = Integer.parseInt(st[j]);\n }\n }\n\n int[][] ans = updateMatrix(arr);\n\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n System.out.print(ans[i][j] + \" \");\n }\n System.out.println();\n }\n\n }\n\n public static int[][] updateMatrix(int[][] matrix) {\n //write your code here\n}\n}\n"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 3\r\n0 0 0\r\n0 1 1\r\n1 1 1\r\n","sampleOutput":"0 0 0 \r\n0 1 1 \r\n1 2 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":"acac84a5-4a80-4354-a880-021a68b0c4f9","name":"Zero One Matrix","slug":"zero-one-matrix","type":1}],"next":{"id":"db14aa97-e1bc-4b0a-9ef8-393e15be61d9","name":"Zero One Matrix MCQ","type":0,"slug":"zero-one-matrix-mcq"},"prev":{"id":"42d0758a-03a2-4f48-9907-5ac48ec9aa78","name":"Number Of Enclaves","type":3,"slug":"number-of-enclaves"}}}

Zero One Matrix

Given an m*n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

{"id":"3719b0f4-558c-41ce-bd5a-ddd7bbd55a9a","name":"Zero One Matrix","description":"Given an m*n binary matrix mat, return the distance of the nearest 0 for each cell.\r\n\r\nThe distance between two adjacent cells is 1.","inputFormat":"First line contains two integers n and m.\r\nEach of next n lines contain m 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\r\n1&lt;= e &lt;= n*(n-1)/2","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<vector<int>> updateMatrix(vector<vector<int>>& matrix){\n // write your code here\n}\n\nint main(){\n \n int n,m;\n cin>>n>>m;\n \n vector<vector<int>>arr(n,vector<int>(m));\n for(int i=0;i<n;i++){\n for(int j=0;j<m;j++){\n int x;\n cin>>x;\n arr[i][j]=x;\n }\n }\n \n vector<vector<int>>ans=updateMatrix(arr);\n \n for(int i=0;i<n;i++){\n for(int j=0;j<m;j++){\n cout<<ans[i][j]<<\" \";\n }\n cout<<endl;\n }\n}"},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.*;\n\nclass Main {\n public static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n String[] st = br.readLine().split(\" \");\n int n = Integer.parseInt(st[0]);\n int m = Integer.parseInt(st[1]);\n\n int[][] arr = new int[n][m];\n\n for (int i = 0; i < n; i++) {\n st = br.readLine().split(\" \");\n for (int j = 0; j < m; j++) {\n arr[i][j] = Integer.parseInt(st[j]);\n }\n }\n\n int[][] ans = updateMatrix(arr);\n\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n System.out.print(ans[i][j] + \" \");\n }\n System.out.println();\n }\n\n }\n\n public static int[][] updateMatrix(int[][] matrix) {\n //write your code here\n}\n}\n"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 3\r\n0 0 0\r\n0 1 1\r\n1 1 1\r\n","sampleOutput":"0 0 0 \r\n0 1 1 \r\n1 2 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":"acac84a5-4a80-4354-a880-021a68b0c4f9","name":"Zero One Matrix","slug":"zero-one-matrix","type":1}],"next":{"id":"db14aa97-e1bc-4b0a-9ef8-393e15be61d9","name":"Zero One Matrix MCQ","type":0,"slug":"zero-one-matrix-mcq"},"prev":{"id":"42d0758a-03a2-4f48-9907-5ac48ec9aa78","name":"Number Of Enclaves","type":3,"slug":"number-of-enclaves"}}}
plane

Editor


Loading...

Zero One Matrix

easy

Given an m*n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

Constraints

1<= n <= 1000 1<= e <= n*(n-1)/2

Format

Input

First line contains two integers n and m. Each of next n lines contain m numbers containing either 0 or 1.

Output

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

Example

Sample Input

3 3 0 0 0 0 1 1 1 1 1

Sample Output

0 0 0 0 1 1 1 2 2

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode