fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <cstring>
  5. using namespace std;
  6. int N, M;
  7. int graph[301][301];
  8. bool visited[301][301];
  9. int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
  10.  
  11. void check(int r, int c ) {
  12. 	queue<pair<int, int>>q;
  13. 	q.push({ r,c });
  14.  
  15. 	while (!q.empty()) {
  16. 		int cr = q.front().first;
  17. 		int cc = q.front().second;
  18. 		q.pop();
  19.  
  20. 		for (int i = 0; i < 4; i++) {
  21. 			int nr = cr + dir[i][0];
  22. 			int nc = cc + dir[i][1];
  23.  
  24. 			if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
  25. 				if (graph[nr][nc] != 0 && !visited[nr][nc]) {
  26. 					q.push({ nr,nc });
  27. 					visited[nr][nc] = true;
  28. 				}
  29. 			}
  30. 		}
  31. 	}
  32. }
  33.  
  34. void bfs(int r, int c) {
  35. 	queue<pair<int, int>>q;
  36. 	q.push({ r,c });
  37.  
  38. 	while (!q.empty()) {
  39. 		int cr = q.front().first;
  40. 		int cc = q.front().second;
  41. 		q.pop();
  42.  
  43. 		for (int i = 0; i < 4; i++) {
  44. 			int nr = cr + dir[i][0];
  45. 			int nc = cc + dir[i][1];
  46.  
  47. 			if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
  48. 				if (graph[nr][nc] == 0 && !visited[nr][nc]) {
  49. 					q.push({ nr,nc });
  50. 					visited[nr][nc] = true;
  51. 				}
  52. 				else if (graph[nr][nc] > 0) {
  53. 					graph[nr][nc]--;
  54. 					visited[nr][nc] = true;
  55. 				}
  56. 			}
  57. 		}
  58. 	}
  59. }
  60.  
  61. int main() {
  62.  
  63. 	ios::sync_with_stdio(false);
  64. 	cin.tie(0);
  65. 	cout.tie(0);
  66. 	cin >> N >> M;
  67. 	for (int i = 0; i < N; i++) {
  68. 		for (int j = 0; j < M; j++) {
  69. 			cin >> graph[i][j];
  70. 			if (i == 0 || i == N - 1 || j == 0 || j == M - 1)
  71. 				graph[i][j] = 0;
  72. 		}
  73. 	}
  74. 	int time = 1;
  75. 	while (true) {
  76.         memset(visited, false, sizeof(visited));
  77.         //빙산 녹이기 0인 구역 탐색
  78. 		for (int i = 0; i < N; i++) {
  79. 			for (int j = 0; j < M; j++) {
  80. 				if (!visited[i][j] && graph[i][j] == 0) {
  81. 					bfs(i, j);
  82. 				}
  83. 			}
  84. 		}
  85.         memset(visited, false, sizeof(visited));
  86.  
  87. 		//나뉘어졌는지, 빙산이 다 녹았는지 검사
  88. 		int cnt = 0;
  89. 		for (int i = 0; i < N; i++) {
  90. 			for (int j = 0; j < M; j++) {
  91. 				if (!visited[i][j] && graph[i][j] != 0) {
  92. 					check(i, j);
  93. 					cnt++;
  94. 				}
  95. 			}
  96. 		}
  97. 		//빙산이 다 녹았다면
  98. 		if (cnt == 0) {
  99. 			cout << 0;
  100. 			break;
  101. 		}
  102. 		//빙산이 두 덩이 이상이라면
  103. 		else if (cnt >= 2) {
  104. 			cout << time;
  105. 			break;
  106. 		}
  107.  
  108. 		time++;
  109. 	}
  110. 	return 0;
  111. }
  112.  
Success #stdin #stdout 0s 5572KB
comments (?)
stdin
copy 
5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0
stdout
copy 
2
https://ideone.com/PzoGCi
language:
C++14 (gcc 8.3)
created:
2 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!