fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. class Solution {
  7. public:
  8.     int numIslands(vector<vector<char>>& grid) {
  9.     	int hi = grid.size(), lo = grid[0].size();
  10.     	int mark[hi][lo];
  11.     	int cnt = 0, min, max;
  12.     	vector<int> marks;
  13.     	for (int i=0; i<hi; i++) 
  14.     		for (int j=0; j<lo; j++) 
  15.     			mark[i][j] = 0;
  16.     	for (int i=0; i<hi; i++)
  17.     		for (int j=0; j<lo; j++) {
  18.     			if (grid[i][j] == '1') {
  19. 	    			min = max = 0;
  20. 	    			if (i>0 && grid[i-1][j] == '1') {
  21. 	    				min = mark[i-1][j];
  22. 	    			}
  23. 	    			if (j>0 && grid[i][j-1] == '1') {
  24. 	    				if (min > mark[i][j-1]) {
  25. 	    					max = min;
  26. 	    					min = mark[i][j-1];
  27. 	    				} else if (min < mark[i][j-1]) {
  28. 	    					max = mark[i][j-1];
  29. 	    					if (min == 0)
  30. 	    						min = max;
  31. 	    				}
  32. 	    			}
  33. 	    			if (max > min) {
  34. 	    				marks.erase(remove(marks.begin(), marks.end(), max), marks.end());
  35. 	    				cout << "#removed  i = " << i << "; j = " << j << "; mark = " << max << "\n";
  36. 	    			}
  37. 	    			if (min > 0) {
  38. 	    				mark[i][j] = min;
  39. 	    				cout << "@assigned old i = " << i << "; j = " << j << "; mark = " << min << "\n";
  40. 	    			} else {
  41. 	    				mark[i][j] = ++cnt;
  42. 	    				marks.push_back(cnt);
  43. 	    				cout << "#assigned new i = " << i << "; j = " << j << "; cnt=" << cnt << ";  mark = " << mark[i][j] << "\n";
  44. 	    			}
  45.     			}
  46.     		}
  47.     	for (int i = 0; i < marks.size(); i++) {
  48.     		cout << marks[i] << "\t";
  49.     	}
  50.     	cout << "\n";
  51.     	return marks.size();
  52.     }
  53. };
  54.  
  55. int main() {
  56. 	// your code goes here
  57. 	Solution x;
  58. 	vector<vector<char>> grid(4, vector<char>());
  59. 	grid[0].push_back('1');
  60. 	grid[0].push_back('1');
  61. 	grid[0].push_back('0');
  62. 	grid[0].push_back('0');
  63. 	grid[0].push_back('0');
  64.  
  65. 	grid[1].push_back('1');
  66. 	grid[1].push_back('1');
  67. 	grid[1].push_back('0');
  68. 	grid[1].push_back('0');
  69. 	grid[1].push_back('0');
  70.  
  71. 	grid[2].push_back('0');
  72. 	grid[2].push_back('0');
  73. 	grid[2].push_back('1');
  74. 	grid[2].push_back('0');
  75. 	grid[2].push_back('0');
  76.  
  77.  
  78. 	grid[3].push_back('0');
  79. 	grid[3].push_back('0');
  80. 	grid[3].push_back('0');
  81. 	grid[3].push_back('1');
  82. 	grid[3].push_back('1');
  83.  
  84.  
  85. 	vector<string> xx(20); int i = 0;
  86. 	xx[i] = "10110010111101011110"; i++;
  87. 	xx[i] = "01001010111111011011"; i++;
  88. 	xx[i] = "10010101011011100110"; i++;
  89. 	xx[i] = "01100110111100100011"; i++;
  90. 	xx[i] = "11010010001010111011"; i++;
  91. 	xx[i] = "00001011001001011110"; i++;
  92. 	xx[i] = "10111101101101110010"; i++;
  93. 	xx[i] = "01100010010111001101"; i++;
  94. 	xx[i] = "00001101001101001010"; i++;
  95. 	xx[i] = "00111010101110111110"; i++;
  96. 	xx[i] = "10101110111010101011"; i++;
  97. 	xx[i] = "00111101110100011101"; i++;
  98. 	xx[i] = "11100000110111011110"; i++;
  99. 	xx[i] = "00111001001111110110"; i++;
  100. 	xx[i] = "00011000011010011111"; i++;
  101. 	xx[i] = "01110100111110111001"; i++;
  102. 	xx[i] = "00001111000010000110"; i++;
  103. 	xx[i] = "11111111110110111111"; i++;
  104. 	xx[i] = "01001001111110101111"; i++;
  105. 	xx[i] = "00111110001111110110"; i++;
  106.  
  107. 	vector<vector<char>> zz(20, vector<char>());
  108.  
  109. 	for (int i=0; i<20; i++) {
  110. 		for (int j=0; j<20; j++) {
  111. 			zz[i].push_back(xx[i][j]);
  112. 		}
  113. 	}
  114.  
  115.  
  116. 	cout << x.numIslands(zz);
  117.  
  118. 	return 0;
  119. }
Success #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
#assigned new i = 0; j = 0; cnt=1;  mark = 1
#assigned new i = 0; j = 2; cnt=2;  mark = 2
@assigned old i = 0; j = 3; mark = 2
#assigned new i = 0; j = 6; cnt=3;  mark = 3
#assigned new i = 0; j = 8; cnt=4;  mark = 4
@assigned old i = 0; j = 9; mark = 4
@assigned old i = 0; j = 10; mark = 4
@assigned old i = 0; j = 11; mark = 4
#assigned new i = 0; j = 13; cnt=5;  mark = 5
#assigned new i = 0; j = 15; cnt=6;  mark = 6
@assigned old i = 0; j = 16; mark = 6
@assigned old i = 0; j = 17; mark = 6
@assigned old i = 0; j = 18; mark = 6
#assigned new i = 1; j = 1; cnt=7;  mark = 7
#assigned new i = 1; j = 4; cnt=8;  mark = 8
@assigned old i = 1; j = 6; mark = 3
@assigned old i = 1; j = 8; mark = 4
@assigned old i = 1; j = 9; mark = 4
@assigned old i = 1; j = 10; mark = 4
@assigned old i = 1; j = 11; mark = 4
@assigned old i = 1; j = 12; mark = 4
#removed  i = 1; j = 13; mark = 5
@assigned old i = 1; j = 13; mark = 4
@assigned old i = 1; j = 15; mark = 6
@assigned old i = 1; j = 16; mark = 6
@assigned old i = 1; j = 18; mark = 6
@assigned old i = 1; j = 19; mark = 6
#assigned new i = 2; j = 0; cnt=9;  mark = 9
#assigned new i = 2; j = 3; cnt=10;  mark = 10
#assigned new i = 2; j = 5; cnt=11;  mark = 11
#assigned new i = 2; j = 7; cnt=12;  mark = 12
@assigned old i = 2; j = 9; mark = 4
@assigned old i = 2; j = 10; mark = 4
@assigned old i = 2; j = 12; mark = 4
@assigned old i = 2; j = 13; mark = 4
@assigned old i = 2; j = 14; mark = 4
#assigned new i = 2; j = 17; cnt=13;  mark = 13
#removed  i = 2; j = 18; mark = 13
@assigned old i = 2; j = 18; mark = 6
#assigned new i = 3; j = 1; cnt=14;  mark = 14
@assigned old i = 3; j = 2; mark = 14
@assigned old i = 3; j = 5; mark = 11
@assigned old i = 3; j = 6; mark = 11
#assigned new i = 3; j = 8; cnt=15;  mark = 15
#removed  i = 3; j = 9; mark = 15
@assigned old i = 3; j = 9; mark = 4
@assigned old i = 3; j = 10; mark = 4
@assigned old i = 3; j = 11; mark = 4
@assigned old i = 3; j = 14; mark = 4
@assigned old i = 3; j = 18; mark = 6
@assigned old i = 3; j = 19; mark = 6
#assigned new i = 4; j = 0; cnt=16;  mark = 16
#removed  i = 4; j = 1; mark = 16
@assigned old i = 4; j = 1; mark = 14
#assigned new i = 4; j = 3; cnt=17;  mark = 17
@assigned old i = 4; j = 6; mark = 11
@assigned old i = 4; j = 10; mark = 4
#assigned new i = 4; j = 12; cnt=18;  mark = 18
@assigned old i = 4; j = 14; mark = 4
@assigned old i = 4; j = 15; mark = 4
@assigned old i = 4; j = 16; mark = 4
@assigned old i = 4; j = 18; mark = 6
@assigned old i = 4; j = 19; mark = 6
#assigned new i = 5; j = 4; cnt=19;  mark = 19
@assigned old i = 5; j = 6; mark = 11
@assigned old i = 5; j = 7; mark = 11
@assigned old i = 5; j = 10; mark = 4
#assigned new i = 5; j = 13; cnt=20;  mark = 20
@assigned old i = 5; j = 15; mark = 4
@assigned old i = 5; j = 16; mark = 4
@assigned old i = 5; j = 17; mark = 4
#removed  i = 5; j = 18; mark = 6
@assigned old i = 5; j = 18; mark = 4
#assigned new i = 6; j = 0; cnt=21;  mark = 21
#assigned new i = 6; j = 2; cnt=22;  mark = 22
@assigned old i = 6; j = 3; mark = 22
#removed  i = 6; j = 4; mark = 22
@assigned old i = 6; j = 4; mark = 19
@assigned old i = 6; j = 5; mark = 19
@assigned old i = 6; j = 7; mark = 11
@assigned old i = 6; j = 8; mark = 11
@assigned old i = 6; j = 10; mark = 4
@assigned old i = 6; j = 11; mark = 4
@assigned old i = 6; j = 13; mark = 20
@assigned old i = 6; j = 14; mark = 20
#removed  i = 6; j = 15; mark = 20
@assigned old i = 6; j = 15; mark = 4
@assigned old i = 6; j = 18; mark = 4
#assigned new i = 7; j = 1; cnt=23;  mark = 23
#removed  i = 7; j = 2; mark = 23
@assigned old i = 7; j = 2; mark = 22
#assigned new i = 7; j = 6; cnt=24;  mark = 24
#assigned new i = 7; j = 9; cnt=25;  mark = 25
@assigned old i = 7; j = 11; mark = 4
@assigned old i = 7; j = 12; mark = 4
#removed  i = 7; j = 13; mark = 20
@assigned old i = 7; j = 13; mark = 4
#assigned new i = 7; j = 16; cnt=26;  mark = 26
@assigned old i = 7; j = 17; mark = 26
#assigned new i = 7; j = 19; cnt=27;  mark = 27
#assigned new i = 8; j = 4; cnt=28;  mark = 28
@assigned old i = 8; j = 5; mark = 28
#assigned new i = 8; j = 7; cnt=29;  mark = 29
#assigned new i = 8; j = 10; cnt=30;  mark = 30
#removed  i = 8; j = 11; mark = 30
@assigned old i = 8; j = 11; mark = 4
@assigned old i = 8; j = 13; mark = 4
@assigned old i = 8; j = 16; mark = 26
#assigned new i = 8; j = 18; cnt=31;  mark = 31
#assigned new i = 9; j = 2; cnt=32;  mark = 32
@assigned old i = 9; j = 3; mark = 32
#removed  i = 9; j = 4; mark = 32
@assigned old i = 9; j = 4; mark = 28
#assigned new i = 9; j = 6; cnt=33;  mark = 33
#assigned new i = 9; j = 8; cnt=34;  mark = 34
@assigned old i = 9; j = 10; mark = 30
#removed  i = 9; j = 11; mark = 30
@assigned old i = 9; j = 11; mark = 4
@assigned old i = 9; j = 12; mark = 4
#assigned new i = 9; j = 14; cnt=35;  mark = 35
@assigned old i = 9; j = 15; mark = 35
#removed  i = 9; j = 16; mark = 35
@assigned old i = 9; j = 16; mark = 26
@assigned old i = 9; j = 17; mark = 26
#removed  i = 9; j = 18; mark = 31
@assigned old i = 9; j = 18; mark = 26
#assigned new i = 10; j = 0; cnt=36;  mark = 36
@assigned old i = 10; j = 2; mark = 32
@assigned old i = 10; j = 4; mark = 28
@assigned old i = 10; j = 5; mark = 28
#removed  i = 10; j = 6; mark = 33
@assigned old i = 10; j = 6; mark = 28
@assigned old i = 10; j = 8; mark = 34
@assigned old i = 10; j = 9; mark = 34
#removed  i = 10; j = 10; mark = 34
@assigned old i = 10; j = 10; mark = 30
@assigned old i = 10; j = 12; mark = 4
@assigned old i = 10; j = 14; mark = 35
@assigned old i = 10; j = 16; mark = 26
@assigned old i = 10; j = 18; mark = 26
@assigned old i = 10; j = 19; mark = 26
@assigned old i = 11; j = 2; mark = 32
@assigned old i = 11; j = 3; mark = 32
#removed  i = 11; j = 4; mark = 32
@assigned old i = 11; j = 4; mark = 28
@assigned old i = 11; j = 5; mark = 28
#assigned new i = 11; j = 7; cnt=37;  mark = 37
#removed  i = 11; j = 8; mark = 37
@assigned old i = 11; j = 8; mark = 34
@assigned old i = 11; j = 9; mark = 34
#assigned new i = 11; j = 11; cnt=38;  mark = 38
#assigned new i = 11; j = 15; cnt=39;  mark = 39
#removed  i = 11; j = 16; mark = 39
@assigned old i = 11; j = 16; mark = 26
@assigned old i = 11; j = 17; mark = 26
@assigned old i = 11; j = 19; mark = 26
#assigned new i = 12; j = 0; cnt=40;  mark = 40
@assigned old i = 12; j = 1; mark = 40
#removed  i = 12; j = 2; mark = 40
@assigned old i = 12; j = 2; mark = 32
@assigned old i = 12; j = 8; mark = 34
@assigned old i = 12; j = 9; mark = 34
@assigned old i = 12; j = 11; mark = 38
@assigned old i = 12; j = 12; mark = 38
@assigned old i = 12; j = 13; mark = 38
@assigned old i = 12; j = 15; mark = 39
#removed  i = 12; j = 16; mark = 39
@assigned old i = 12; j = 16; mark = 26
@assigned old i = 12; j = 17; mark = 26
@assigned old i = 12; j = 18; mark = 26
@assigned old i = 13; j = 2; mark = 32
@assigned old i = 13; j = 3; mark = 32
@assigned old i = 13; j = 4; mark = 32
#assigned new i = 13; j = 7; cnt=41;  mark = 41
#assigned new i = 13; j = 10; cnt=42;  mark = 42
#removed  i = 13; j = 11; mark = 42
@assigned old i = 13; j = 11; mark = 38
@assigned old i = 13; j = 12; mark = 38
@assigned old i = 13; j = 13; mark = 38
@assigned old i = 13; j = 14; mark = 38
#removed  i = 13; j = 15; mark = 39
@assigned old i = 13; j = 15; mark = 38
@assigned old i = 13; j = 17; mark = 26
@assigned old i = 13; j = 18; mark = 26
@assigned old i = 14; j = 3; mark = 32
@assigned old i = 14; j = 4; mark = 32
#assigned new i = 14; j = 9; cnt=43;  mark = 43
#removed  i = 14; j = 10; mark = 43
@assigned old i = 14; j = 10; mark = 42
@assigned old i = 14; j = 12; mark = 38
@assigned old i = 14; j = 15; mark = 38
@assigned old i = 14; j = 16; mark = 38
#removed  i = 14; j = 17; mark = 38
@assigned old i = 14; j = 17; mark = 26
@assigned old i = 14; j = 18; mark = 26
@assigned old i = 14; j = 19; mark = 26
#assigned new i = 15; j = 1; cnt=44;  mark = 44
@assigned old i = 15; j = 2; mark = 44
#removed  i = 15; j = 3; mark = 44
@assigned old i = 15; j = 3; mark = 32
#assigned new i = 15; j = 5; cnt=45;  mark = 45
#assigned new i = 15; j = 8; cnt=46;  mark = 46
#removed  i = 15; j = 9; mark = 46
@assigned old i = 15; j = 9; mark = 43
#removed  i = 15; j = 10; mark = 43
@assigned old i = 15; j = 10; mark = 42
@assigned old i = 15; j = 11; mark = 42
#removed  i = 15; j = 12; mark = 42
@assigned old i = 15; j = 12; mark = 38
#assigned new i = 15; j = 14; cnt=47;  mark = 47
#removed  i = 15; j = 15; mark = 47
@assigned old i = 15; j = 15; mark = 38
@assigned old i = 15; j = 16; mark = 38
@assigned old i = 15; j = 19; mark = 26
#assigned new i = 16; j = 4; cnt=48;  mark = 48
#removed  i = 16; j = 5; mark = 48
@assigned old i = 16; j = 5; mark = 45
@assigned old i = 16; j = 6; mark = 45
@assigned old i = 16; j = 7; mark = 45
@assigned old i = 16; j = 12; mark = 38
#assigned new i = 16; j = 17; cnt=49;  mark = 49
@assigned old i = 16; j = 18; mark = 49
#assigned new i = 17; j = 0; cnt=50;  mark = 50
@assigned old i = 17; j = 1; mark = 50
@assigned old i = 17; j = 2; mark = 50
@assigned old i = 17; j = 3; mark = 50
#removed  i = 17; j = 4; mark = 50
@assigned old i = 17; j = 4; mark = 48
#removed  i = 17; j = 5; mark = 48
@assigned old i = 17; j = 5; mark = 45
@assigned old i = 17; j = 6; mark = 45
@assigned old i = 17; j = 7; mark = 45
@assigned old i = 17; j = 8; mark = 45
@assigned old i = 17; j = 9; mark = 45
#assigned new i = 17; j = 11; cnt=51;  mark = 51
#removed  i = 17; j = 12; mark = 51
@assigned old i = 17; j = 12; mark = 38
#assigned new i = 17; j = 14; cnt=52;  mark = 52
@assigned old i = 17; j = 15; mark = 52
@assigned old i = 17; j = 16; mark = 52
#removed  i = 17; j = 17; mark = 52
@assigned old i = 17; j = 17; mark = 49
@assigned old i = 17; j = 18; mark = 49
@assigned old i = 17; j = 19; mark = 49
@assigned old i = 18; j = 1; mark = 50
@assigned old i = 18; j = 4; mark = 48
@assigned old i = 18; j = 7; mark = 45
@assigned old i = 18; j = 8; mark = 45
@assigned old i = 18; j = 9; mark = 45
@assigned old i = 18; j = 10; mark = 45
#removed  i = 18; j = 11; mark = 51
@assigned old i = 18; j = 11; mark = 45
#removed  i = 18; j = 12; mark = 45
@assigned old i = 18; j = 12; mark = 38
@assigned old i = 18; j = 14; mark = 52
@assigned old i = 18; j = 16; mark = 52
#removed  i = 18; j = 17; mark = 52
@assigned old i = 18; j = 17; mark = 49
@assigned old i = 18; j = 18; mark = 49
@assigned old i = 18; j = 19; mark = 49
#assigned new i = 19; j = 2; cnt=53;  mark = 53
@assigned old i = 19; j = 3; mark = 53
#removed  i = 19; j = 4; mark = 53
@assigned old i = 19; j = 4; mark = 48
@assigned old i = 19; j = 5; mark = 48
@assigned old i = 19; j = 6; mark = 48
@assigned old i = 19; j = 10; mark = 45
@assigned old i = 19; j = 11; mark = 45
#removed  i = 19; j = 12; mark = 45
@assigned old i = 19; j = 12; mark = 38
@assigned old i = 19; j = 13; mark = 38
#removed  i = 19; j = 14; mark = 52
@assigned old i = 19; j = 14; mark = 38
@assigned old i = 19; j = 15; mark = 38
@assigned old i = 19; j = 17; mark = 49
@assigned old i = 19; j = 18; mark = 49
1	2	3	4	7	8	9	10	11	12	14	17	18	19	21	24	25	26	27	28	29	36	41	49	
24
https://ideone.com/iaETB1
language:
C++14 (gcc 8.3)
created:
8 years 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!