fork(28) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int n, m;
  5. int seawater[102][102];
  6. int Hmax=0;
  7. void read ()
  8. {
  9. 	for (int i=1; i<=n; i++)
  10. 	{
  11. 		for (int j=1; j<=m; j++)
  12. 		{
  13. 			cin>>seawater[i][j];
  14. 			if (seawater[i][j]>Hmax) Hmax=seawater[i][j];
  15. 		}
  16. 	}
  17. }
  18.  
  19. int check[102][102];
  20. int check_connect[102][102];
  21. void init ()
  22. {
  23. 	for (int i=1; i<=n; i++)
  24. 	{
  25. 		for (int j=1; j<=m; j++)
  26. 		{
  27. 			check[i][j]=0;
  28. 			check_connect[i][j]=0;
  29. 		}
  30. 	}
  31. }
  32.  
  33. int extra;
  34. int x_ar[]={+1, +0, -1, +0};
  35. int y_ar[]={+0, -1, +0, +1};
  36. void loang (int i, int j)
  37. {
  38. 	check[i][j]=1;
  39. 	for (int k=0; k<4; k++)
  40. 	{
  41. 		int X=j+x_ar[k];
  42. 		int Y=i+y_ar[k];
  43. 		if (X>=1 && X<=m && Y>=1 && Y<=n)
  44. 		{
  45. 			if (check[Y][X]==0 && seawater[Y][X]<=extra) loang (Y, X);
  46. 		}
  47. 	}
  48. }
  49.  
  50. void DFS (int i, int j)
  51. {
  52. 	check_connect[i][j]=1;
  53. 	for (int k=0; k<4; k++)
  54. 	{
  55. 		int X=j+x_ar[k];
  56. 		int Y=i+y_ar[k];
  57. 		if (X>=1 && X<=m && Y>=1 && Y<=n)
  58. 		{
  59. 			if (check_connect[Y][X]==0 && check[Y][X]==check[i][j]) DFS (Y, X);
  60. 		}
  61. 	}
  62. }
  63.  
  64. int main ()
  65. {
  66. 	int t=0;
  67. 	while (1)
  68. 	{
  69. 		cin>>n>>m;
  70. 		if (n==0 && m==0) break;
  71. 		t++;
  72. 		read ();
  73. 		int kt=0;
  74. 		for (int k=0; k<=Hmax; k++)
  75. 		{
  76. 			extra=k;
  77. 			init ();
  78. 			for (int i=1; i<=n; i++)
  79. 			{
  80. 				for (int j=1; j<=m; j++)
  81. 				{
  82. 					if ((i==1 || i==n || j==1 || j==m) && seawater[i][j]<=k && check[i][j]==0) loang (i, j);
  83. 				}
  84. 			}
  85. 			//dem lien thong?
  86. 			int count_connect=0;
  87. 			for (int i=1; i<=n; i++)
  88. 			{
  89. 				for (int j=1; j<=m; j++)
  90. 				{
  91. 					if (check_connect[i][j]==0 && check[i][j]==0)
  92. 					{
  93. 						count_connect++;
  94. 						DFS (i, j);
  95. 					}
  96. 				}
  97. 			}
  98. 			if (count_connect>1)
  99. 			{
  100. 				kt=1;
  101. 				break;
  102. 			}
  103. 		}
  104. 		if (kt==1) cout<<"Case "<<t<<": Island splits when ocean rises "<<extra<<" feet."<<endl;
  105. 		else cout<<"Case "<<t<<": Island never splits."<<endl;
  106. 	}
  107. 	return 0;
  108. }
Success #stdin #stdout 0s 16184KB
comments (?)
stdin
copy 
5 5
3 4 3 0 0
3 5 5 4 3
2 5 4 4 3
1 3 0 0 0
1 2 1 0 0

5 5
5 5 5 5 7
4 1 1 1 4
4 1 2 1 3
7 1 0 0 4
7 3 4 4 4

0 0
stdout
copy 
Case 1: Island never splits.
Case 2: Island splits when ocean rises 3 feet.
https://ideone.com/rJSQ3q
v- BCISLAND - Nước biển
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!