fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class DSU
  5. {
  6. 	public:
  7. 	unordered_map<string,string> parent;
  8. 	unordered_map<string, int> sz;
  9.  
  10. 	string getKey(long x,long y)
  11. 	{
  12. 		return to_string(x) +"_"+ to_string(y);
  13. 	}
  14.  
  15. 	string findParent(string key)
  16. 	{
  17. 		if(parent[key]==key)
  18. 		return key;
  19. 		else
  20. 		{
  21. 		parent[key] = findParent(parent[key]);
  22. 		return parent[key];
  23. 		}
  24.  
  25. 	}
  26.  
  27. 	bool unite(long x1,long y1,long x,long y)
  28. 	{
  29. 		string parentKey = findParent(getKey(x,y));
  30. 		string parentKey1 = findParent(getKey(x1,y1));
  31. 		if(parentKey==parentKey1)
  32. 			return false;
  33. 		else
  34. 		{
  35. 			if (sz[parentKey] < sz[parentKey1]) {
  36.             parent[parentKey] = parentKey1;
  37.             sz[parentKey1] += sz[parentKey];
  38.         } else {
  39.             parent[parentKey1] = parentKey;
  40.             sz[parentKey] += sz[parentKey1];
  41.         }
  42. 			return true;
  43. 		}
  44. 	}
  45. };
  46.  
  47. class Grid
  48. {
  49. 	public:
  50. 	unordered_set<string> landLoc;
  51. 	DSU dsuObj;
  52. 	long islandCount=0;
  53. 	vector<vector<long>> dir = {{1,0},{0,1},{-1,0},{0,-1}};
  54.  
  55. 	string getKey(long x,long y)
  56. 	{
  57. 		return to_string(x) +"_"+ to_string(y);
  58. 	}
  59.  
  60. 	void addLand(long x, long y)
  61. 	{
  62. 		string key = getKey(x,y);
  63. 		if(!landLoc.count(key))
  64. 		{
  65. 			landLoc.insert(key);
  66. 			dsuObj.parent[key] =key;
  67. 			dsuObj.sz[key]=1;
  68. 			islandCount++;
  69. 			for(int k=0;k<=3;k++)
  70. 			{
  71. 				long newX = x+ dir[k][0];
  72. 				long newY = y + dir[k][1];
  73. 				string newKey = getKey(newX,newY);
  74. 				if(landLoc.count(newKey))
  75. 				{
  76. 					bool isSuccess = dsuObj.unite(x,y,newX,newY);
  77. 					if(isSuccess)
  78. 					{
  79. 						islandCount--;
  80. 					}
  81. 				}
  82. 			}
  83.  
  84. 		}
  85.  
  86. 	}
  87.  
  88. 	bool isLand(long x,long y)
  89. 	{
  90. 		string key = to_string(x) +"_"+ to_string(y);
  91. 		if(landLoc.count(key))
  92. 		{
  93. 			return true;
  94. 		}
  95. 		else
  96. 		return false;
  97. 	}
  98.  
  99. 	long getNumberofIsland()
  100. 	{
  101. 		return islandCount;
  102. 	}
  103.  
  104. };
  105.  
  106. int main() {
  107. 	// your code goes here
  108. 	Grid stringMap;
  109.     stringMap.addLand(5, 10);
  110.     stringMap.addLand(5, 11);
  111.     stringMap.addLand(2, 11);
  112.     stringMap.addLand(3, 11);
  113.     stringMap.addLand(4, 11);
  114.  
  115.     cout << "Is (5, 10) land? " << (stringMap.isLand(5, 10) ? "Yes" : "No") << endl;
  116.     cout << "Is (5, 11) land? " << (stringMap.isLand(5, 11) ? "Yes" : "No") << endl;
  117. 	cout<<"Count of lands:"<<stringMap.getNumberofIsland()<<endl;
  118.     return 0;
  119. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Is (5, 10) land? Yes
Is (5, 11) land? Yes
Count of lands:1
https://ideone.com/kzO2R4
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!