#include #include #include #include #include using namespace std; struct Data { int x_coord; int y_coord; int cost; }; int bfs(vector>& map, const int t_row, const int t_col, queue& waiting) { int x; int y; int cost; while (!waiting.empty()) { // 작업 할 것 없을때까지 돌려! x = waiting.front().x_coord; y = waiting.front().y_coord; cost = waiting.front().cost; waiting.pop(); // 데이터 뽑고 팝 if (map[y][x] > 0) continue; // 이미 확인된 익은 토마토면 패스 if (x == 0 || x == t_col+1) continue; // 테두리 건들지마! if (y == 0 || y == t_row+1) continue; // 테두리 건들지마! map[y][x] = cost; // 미확인 익은 토마토면 코스트 할당해줌 // 주변 미숙 토마토(-1) 작업큐에 할당 if (map[y][x + 1] == -1) { waiting.push({ x + 1,y,cost + 1 }); } if (map[y][x - 1] == -1) { waiting.push({ x - 1,y,cost + 1 }); } if (map[y + 1][x] == -1) { waiting.push({ x,y + 1,cost + 1 }); } if (map[y - 1][x] == -1) { waiting.push({ x,y - 1,cost + 1 }); } } return cost-1; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t_row, t_col; cin >> t_col >> t_row; vector> map; // map 초기화 map.resize(t_row + 2, vector (t_col+2)); for (int i = 0; i <= t_row + 1; i++) { for (int j = 0; j <= t_col + 1; j++) { map[i][j] = -2; // 기본적으로 벽 처리 } } queue waiting; // 작업 대기 큐 for (int i = 1; i <= t_row; i++) { for (int j = 1; j <= t_col; j++) { cin >> map[i][j]; map[i][j]--; // 벽이면 -2 미숙토마토면 -1 익은토마토면 0 if (map[i][j] == 0) { // 미확인 익은 토마토 확인 시 작업 큐에 삽입 waiting.push({ j,i,1 }); // 시작 코스트를 1로 했음. 나중에 1빼주면 답 나옴 } } } int ans = bfs(map, t_row, t_col, waiting); // bfs끝났을 때 코스트 반환 for (int i = 1; i <= t_row; i++) { for (int j = 1; j <= t_col; j++) { if (map[i][j] == -1) { // 안익은 토마토 있으면 -1 출력 ans = -1; } } } cout << ans; return 0; }

제출 #147917

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: