fork(1) download
  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
stdin
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
Case 1: Island never splits.
Case 2: Island splits when ocean rises 3 feet.