#include #include #include using namespace std; int M, N; int matrix[51][51]; int dist[51][51]; int dr[4] = { -1,0,1,0 }; int dc[4] = { 0,-1,0,1 }; void bfs(int r, int c) { queue> q; q.push({ r,c }); dist[r][c] = 0; while (true) { if (q.empty()) { break; } pair cur = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nr = cur.first + dr[i]; int nc = cur.second + dc[i]; if (nr >= 0 && nc >= 0 && nr < N && nc < M) { if (matrix[nr][nc] == 0) { q.push({ nr,nc }); matrix[nr][nc] = 1;//토마토 익음 dist[nr][nc] = dist[cur.first][cur.second] + 1; //cout << nr<<',' << nc <<"가 익은 일차: "<< dist[nr][nc] << endl; } } } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> M >> N;//M-가로, N-세로 if (M > 50 || N > 50) return 0;//예외처리 int input; for (int r = 0; r < N; r++) { for (int c = 0; c < M; c++) { cin >> input; matrix[r][c] = input; dist[r][c] = -1; } } for (int r = 0; r < N; r++) { for (int c = 0; c < M; c++) { if (matrix[r][c] == 1 && dist[r][c] == -1) {//자기혼자 원래 익어있던 토마토 bfs(r, c); } } } /* for (int r = 0; r < N; r++) { for (int c = 0; c < M; c++) { cout << dist[r][c] << ' '; } cout << endl; } */ int biggest = -1; for (int r = 0; r < N; r++) { for (int c = 0; c < M; c++) { if (matrix[r][c] == 0) { cout << "-1"; return 0; }//모두익지는 못했다면 -1출력 if (dist[r][c] > biggest) { biggest = dist[r][c]; } } } cout << biggest; return 0; } /* 일수 재기: 구역마다 재는건 당연히 초기화 한 구역 끝나면 biggest랑 비교후 더큰쪽으로. 익힐 토마토?: 메인함수에서 bfs호출하는건 익은거 1 찾기. bfs안에서 전염시킬거 찾는건 안익은거 0 찾기 --- 끝까지 못익는게 있다면 -1 출력<-이거 빠짐 --- ?????아 이거 일수 세는거 너무 곤란한데;;이거 dfs로 푸는건가? 근데 dfs로만 풀수 있는건 없다하지 않았나..? 일수 세는게 결국 한번에 한칸씩 보면서 확장시키는거니까 같은날 a라는 칸에서 확장된애들이랑 b라는 칸에서 확장된 애들은 그냥 하루인건데 이걸 하루로 칠수가없네... 다시말해 큐에서 하나씩 뽑아쓰면서 확장하는거다보니 한번에 큐에 넣은 애들 (최대 4개)를 같은 세대로 묶을수가... 아 이 세대 표현 어떻게 하나했더니... ->visit대신 세대 matrix가 있고 (현재칸의 세대)+1을 상하좌우 같은 칸에 넣는거임. 그러고는 bfs함수가 세대 리턴할것도 없이 그냥 세대 매트릭스 중 최댓값 출력하면 됨. */

제출 #163133

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: