{"id":"18f271dc-7688-431e-9f1c-f86325ad0df6","name":"Number Of Island 2","description":"Given an m*n matrix mat, Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid mat[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.You need to return an array of size K.","inputFormat":"First line contains three integers m and n and k.\r\nEach of next k lines contain 2 numbers denoting row and col to change into 1.","outputFormat":"print number of island after each operation.","constraints":"1&lt;= m,n &lt;= 10000\r\n1&lt;= k &lt;= 10^6","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\n\n\nvector<int>numIslands2(int m,int n, vector<vector<int>>& pos){\n // write your code here\n}\n\nint main(){\n int m,n,q;\n cin>>m>>n>>q;\n \n vector<vector<int>>pos(q,vector<int>(2));\n \n for(int i=0;i<q;i++){\n cin>>pos[i][0];\n cin>>pos[i][1];\n }\n vector<int>ans=numIslands2(m, n, pos);\n \n cout<<\"[\";\n for(int i=0;i<ans.size();i++){\n if(i==ans.size()-1)\n cout<<ans[i];\n else\n cout<<ans[i]<<\", \";\n }\n cout<<\"]\";\n }"},"java":{"code":"\r\nimport java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n public static void main(String[] args) throws NumberFormatException, IOException {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n String[] st = br.readLine().split(\" \");\r\n int m = Integer.parseInt(st[0]);\r\n int n = Integer.parseInt(st[1]);\r\n int q = Integer.parseInt(st[2]);\r\n\r\n int[][] pos = new int[q][2];\r\n for (int i = 0; i < q; i++) {\r\n st = br.readLine().split(\" \");\r\n pos[i][0] = Integer.parseInt(st[0]);\r\n pos[i][1] = Integer.parseInt(st[1]);\r\n }\r\n\r\n System.out.println(numIslands2(m, n, pos));\r\n }\r\n\r\n public static List<Integer> numIslands2(int m, int n, int[][] positions) {\r\n\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 3 4\r\n0 0\r\n0 1\r\n1 2\r\n2 1\r\n","sampleOutput":"[1, 1, 2, 3]\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":"7e6af903-c512-453c-adaa-9a49a4917097","name":"Number Of Island 2","slug":"number-of-island-2","type":1}],"next":{"id":"7eadeccf-8289-4030-8a65-49d57fab6ed4","name":"Number of Island 2 MCQ","type":0,"slug":"number-of-island-2-mcq"},"prev":{"id":"aeb73c41-1b18-4eff-b427-237b9082016b","name":"Accounts Merge","type":3,"slug":"accounts-merge"}}}

Number Of Island 2

Given an m*n matrix mat, Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid mat[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.You need to return an array of size K.

{"id":"18f271dc-7688-431e-9f1c-f86325ad0df6","name":"Number Of Island 2","description":"Given an m*n matrix mat, Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid mat[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.You need to return an array of size K.","inputFormat":"First line contains three integers m and n and k.\r\nEach of next k lines contain 2 numbers denoting row and col to change into 1.","outputFormat":"print number of island after each operation.","constraints":"1&lt;= m,n &lt;= 10000\r\n1&lt;= k &lt;= 10^6","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\n\n\nvector<int>numIslands2(int m,int n, vector<vector<int>>& pos){\n // write your code here\n}\n\nint main(){\n int m,n,q;\n cin>>m>>n>>q;\n \n vector<vector<int>>pos(q,vector<int>(2));\n \n for(int i=0;i<q;i++){\n cin>>pos[i][0];\n cin>>pos[i][1];\n }\n vector<int>ans=numIslands2(m, n, pos);\n \n cout<<\"[\";\n for(int i=0;i<ans.size();i++){\n if(i==ans.size()-1)\n cout<<ans[i];\n else\n cout<<ans[i]<<\", \";\n }\n cout<<\"]\";\n }"},"java":{"code":"\r\nimport java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n public static void main(String[] args) throws NumberFormatException, IOException {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n String[] st = br.readLine().split(\" \");\r\n int m = Integer.parseInt(st[0]);\r\n int n = Integer.parseInt(st[1]);\r\n int q = Integer.parseInt(st[2]);\r\n\r\n int[][] pos = new int[q][2];\r\n for (int i = 0; i < q; i++) {\r\n st = br.readLine().split(\" \");\r\n pos[i][0] = Integer.parseInt(st[0]);\r\n pos[i][1] = Integer.parseInt(st[1]);\r\n }\r\n\r\n System.out.println(numIslands2(m, n, pos));\r\n }\r\n\r\n public static List<Integer> numIslands2(int m, int n, int[][] positions) {\r\n\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 3 4\r\n0 0\r\n0 1\r\n1 2\r\n2 1\r\n","sampleOutput":"[1, 1, 2, 3]\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":"7e6af903-c512-453c-adaa-9a49a4917097","name":"Number Of Island 2","slug":"number-of-island-2","type":1}],"next":{"id":"7eadeccf-8289-4030-8a65-49d57fab6ed4","name":"Number of Island 2 MCQ","type":0,"slug":"number-of-island-2-mcq"},"prev":{"id":"aeb73c41-1b18-4eff-b427-237b9082016b","name":"Accounts Merge","type":3,"slug":"accounts-merge"}}}
plane

Editor


Loading...

Number Of Island 2

easy

Given an m*n matrix mat, Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid mat[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.You need to return an array of size K.

Constraints

1<= m,n <= 10000 1<= k <= 10^6

Format

Input

First line contains three integers m and n and k. Each of next k lines contain 2 numbers denoting row and col to change into 1.

Output

print number of island after each operation.

Example

Sample Input

3 3 4 0 0 0 1 1 2 2 1

Sample Output

[1, 1, 2, 3]

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode