{"id":"9263143a-484f-4e27-8ff4-c5f3f4020b4b","name":"Number Of Distinct Island","description":"Given an m*n binary matrix mat, return the number of distinct island.\r\n\r\nAn island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.","inputFormat":"First line contains two integers n and m.\r\nEach of next n lines contain n numbers containing either 0 or 1.","outputFormat":"print number of distinct island.","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;\nstring psf;\n\nint numDistinctIslands(vector<vector<int>>& arr){\n //write your code here\n}\n\nint main(){\n int n,m;\n cin>>n>>m;\n \n vector<vector<int>>arr(n,vector<int>(m));\n \n for(int i=0;i<n;i++){\n for(int j=0;j<m;j++){\n int x;\n cin>>x;\n \n arr[i][j]=x;\n }\n }\n cout<<numDistinctIslands(arr);\n}"},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.*;\n\nclass Main {\n\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 System.out.println(numDistinctIslands(arr));\n\n }\n\n public static StringBuilder psf = new StringBuilder();\n\n public static int numDistinctIslands(int[][] arr) {\n //write your code here\n }\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 3\r\n1 0 0\r\n0 1 0\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":"262038a5-000d-4658-b853-f6121abac4a5","name":"Number Of Distinct Island","slug":"number-of-distinct-island","type":1}],"next":{"id":"3fb19fa4-67b0-4b10-8c34-687ba3eb877e","name":"Number of Distinct Island","type":0,"slug":"number-of-distinct-island"},"prev":{"id":"0ba1a1ab-9b31-4382-b603-e5694835ebd5","name":"(0-1) Matrix","type":3,"slug":"0-1-matrix"}}}

Number Of Distinct Island

Given an m*n binary matrix mat, return the number of distinct island. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

{"id":"9263143a-484f-4e27-8ff4-c5f3f4020b4b","name":"Number Of Distinct Island","description":"Given an m*n binary matrix mat, return the number of distinct island.\r\n\r\nAn island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.","inputFormat":"First line contains two integers n and m.\r\nEach of next n lines contain n numbers containing either 0 or 1.","outputFormat":"print number of distinct island.","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;\nstring psf;\n\nint numDistinctIslands(vector<vector<int>>& arr){\n //write your code here\n}\n\nint main(){\n int n,m;\n cin>>n>>m;\n \n vector<vector<int>>arr(n,vector<int>(m));\n \n for(int i=0;i<n;i++){\n for(int j=0;j<m;j++){\n int x;\n cin>>x;\n \n arr[i][j]=x;\n }\n }\n cout<<numDistinctIslands(arr);\n}"},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.*;\n\nclass Main {\n\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 System.out.println(numDistinctIslands(arr));\n\n }\n\n public static StringBuilder psf = new StringBuilder();\n\n public static int numDistinctIslands(int[][] arr) {\n //write your code here\n }\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 3\r\n1 0 0\r\n0 1 0\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":"262038a5-000d-4658-b853-f6121abac4a5","name":"Number Of Distinct Island","slug":"number-of-distinct-island","type":1}],"next":{"id":"3fb19fa4-67b0-4b10-8c34-687ba3eb877e","name":"Number of Distinct Island","type":0,"slug":"number-of-distinct-island"},"prev":{"id":"0ba1a1ab-9b31-4382-b603-e5694835ebd5","name":"(0-1) Matrix","type":3,"slug":"0-1-matrix"}}}
plane

Editor


Loading...

Number Of Distinct Island

easy

Given an m*n binary matrix mat, return the number of distinct island. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

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 n numbers containing either 0 or 1.

Output

print number of distinct island.

Example

Sample Input

3 3 1 0 0 0 1 0 1 1 1

Sample Output

2

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode