fork download 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. int graph[1000001][5]; //모든 수의 상,하,좌,우에 연결돼 있는 것들을 저장하는 그래프!
  5. int BFSvisit[1000001];
  6. int queue[1000001] = { 0 }; //큐를 사용했습니다
  7. int front = 1;
  8. int rear = 1;
  9.  
  10. void BFS(int m) { //BFS~~
  11. 	int temp;
  12. 	while (front < rear) {
  13. 		temp = queue[front];
  14. 		if (graph[temp][1] == 0 && BFSvisit[temp + 1] == -1) { //탐색하는 그래프의 오른쪽에 안익은 감이 있다??
  15. 			BFSvisit[temp + 1] = BFSvisit[temp] + 1;
  16. 			queue[rear] = temp + 1;
  17. 			rear++;
  18. 		}
  19. 		if (graph[temp][2] == 0 && BFSvisit[temp - 1] == -1) { //탐색하는 그래프의 왼쪽에 안익은 감이 있다??
  20. 			BFSvisit[temp - 1] = BFSvisit[temp] + 1;
  21. 			queue[rear] = temp - 1;
  22. 			rear++;
  23. 		}
  24. 		if (graph[temp][3] == 0 && BFSvisit[temp - m] == -1) { //탐색하는 그래프의 위쪽에 안익은 감이 있다??
  25. 			BFSvisit[temp - m] = BFSvisit[temp] + 1;
  26. 			queue[rear] = temp - m;
  27. 			rear++;
  28. 		}
  29. 		if (graph[temp][4] == 0 && BFSvisit[temp + m] == -1) { //탐색하는 그래프의 아랫쪽에 안익은 감이 있다??
  30. 			BFSvisit[temp + m] = BFSvisit[temp] + 1;
  31. 			queue[rear] = temp + m;
  32. 			rear++;
  33. 		}
  34. 		front++;
  35. 	}
  36. }
  37.  
  38.  
  39.  
  40.  
  41. int main() {
  42. 	int i, j, m, n;
  43. 	int flag = 0;
  44. 	int** read;
  45. 	int big;
  46. 	scanf("%d %d", &m, &n);
  47.  
  48. 	read = (int**)malloc(sizeof(int*) * (n + 2));
  49. 	for (i = 0; i < n + 2; i++) {
  50. 		read[i] = (int*)malloc(sizeof(int) * (m + 2));
  51. 	}//리드 배열 생성
  52. 	for (i = 0; i < 1000001; i++) {
  53. 		for (j = 0; j < 5; j++) {
  54. 			graph[i][j] = -1;
  55. 		}
  56. 		BFSvisit[i] = -1;
  57. 	}//그래프,bfsvisit을 -1로 초기화 시킨다
  58.  
  59. 	for (i = 1; i < n + 1; i++) {//입력받기 시작
  60. 		for (j = 1; j < m + 1; j++) {
  61. 			scanf("%d", &read[i][j]);
  62. 			graph[m * (i - 1) + j][0] = read[i][j];
  63. 			if (read[i][j] == 1) { //1인 것이 있으면 바로 큐에 넣었어요
  64. 				queue[rear] = m * (i - 1) + j;
  65. 				BFSvisit[m * (i - 1) + j] = 0; //그리고 이것들의 비지트는 0으로 초기화
  66. 				rear++;
  67. 			}
  68. 			if (read[i][j] == 0)
  69. 				flag = 1; //나중에 익은 토마토가 없을때 -1을 출력하기 위해
  70.  
  71. 		}
  72. 	}
  73. 	for (i = 1; i < n + 1; i++) {
  74. 		for (j = 1; j < m + 1; j++) {
  75. 			graph[m * (i - 1) + j][1] = read[i][j + 1];
  76. 			graph[m * (i - 1) + j][2] = read[i][j - 1];
  77. 			graph[m * (i - 1) + j][3] = read[i - 1][j];
  78. 			graph[m * (i - 1) + j][4] = read[i + 1][j];
  79.  
  80. 		}//그래프에 리드를 넣었어요
  81. 	}
  82. 	if (rear == 1) {
  83. 		if (flag == 1)
  84. 			printf("-1");
  85. 		else
  86. 			printf("0");
  87. 		return 0;
  88. 	} //예외들 출력~
  89. 	if (rear == n * m + 1) {
  90. 		printf("0");
  91. 		return 0;
  92. 	} //여기도 예외 출력~
  93. 	BFS(m); //BFS시작했습니다!
  94. 	big = 0; //결과 값을 구하려고요
  95. 	for (i = 1; i < n + 1; i++) {
  96. 		for (j = 1; j < m + 1; j++) {
  97. 			if (graph[m * (i - 1) + j][0] == 0 && BFSvisit[m * (i - 1) + j] == -1) { //격리구간이 있었을 시 -1출력후 끝
  98. 				printf("-1");
  99. 				return 0;
  100. 			}
  101. 			if (big < BFSvisit[m * (i - 1) + j])
  102. 				big = BFSvisit[m * (i - 1) + j]; //가장 큰 수를 저장했어요.
  103. 		}
  104. 	}
  105. 	printf("%d", big);
  106. }
  107.  
Success #stdin #stdout 0s 36768KB
comments (?)
stdin 
6 5
0 0 0 0 0 0
-1 -1 -1 -1 -1 0
0 0 0 0 0 0
0 -1 -1 -1 -1 -1
0 0 0 0 0 1
stdout 
12
https://ideone.com/1U3MZk
language:
C (gcc 8.3)
created:
4 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!