#include #include #include using namespace std; typedef struct POINT { int x; int y; }POINT; int g_N; int g_Map[20][20]; // 입력 데이터 int g_Check[20][20]; // 순회 체크 POINT g_pish; // 상어가 먹을 고기의 위치 POINT g_shark; // 상어의 위치 int g_size = 2; // 상어의 크기 int g_eat_count; // 상어가 먹은 고기의 개수 (현재 크기 기준) int g_time; // 고기를 먹는데 걸리는 시간 (초) int g_sum_time; // 총 걸리는 시간 (초) queue g_queue_point; // 너비우선 탐색에 활용할 큐 queue g_queue_level; // 너비우선 탐색에 활용할 큐 void ClearCheck(); void StartSearch(POINT shark); void IsEdible(POINT point, int time); int main() { QCoreApplication app(argc, argv); // Coding Area cin >> g_N; for(int i = 0; i < g_N; i++) { for(int j = 0; j < g_N; j++) { cin >> g_Map[i][j]; if(g_Map[i][j] == 9) { g_Map[i][j] = 0; g_shark = POINT{j, i}; } } } while(1) { g_pish = POINT{20, 20}; g_time = 400; ClearCheck(); StartSearch(g_shark); if(g_pish.x >= 20 || g_pish.y >= 20) break; g_Map[g_pish.y][g_pish.x] = 0; g_shark = g_pish; g_sum_time += g_time; if(++g_eat_count >= g_size) { g_eat_count = 0; g_size++; } } cout << g_sum_time; // return 0; } void ClearCheck() { for(int i = 0; i < g_N; i++) { for(int j = 0; j < g_N; j++) { g_Check[i][j] = 0; } } } void StartSearch(POINT shark) { g_Check[shark.y][shark.x] = 1; g_queue_level.push(0); while(1) { int time = g_queue_level.front(); g_queue_level.pop(); // 우 IsEdible(POINT{shark.x + 1, shark.y}, time + 1); // 하 IsEdible(POINT{shark.x, shark.y + 1}, time + 1); // 좌 IsEdible(POINT{shark.x - 1, shark.y}, time + 1); // 상 IsEdible(POINT{shark.x, shark.y - 1}, time + 1); if(g_queue_point.empty()) break; shark = g_queue_point.front(); g_queue_point.pop(); } } void IsEdible(POINT point, int time) { if(point.x < 0 || point.y < 0 || point.x >= g_N || point.y >= g_N) return; if(g_Check[point.y][point.x]) return; g_Check[point.y][point.x] = 1; if(g_Map[point.y][point.x] > g_size) return; if(g_Map[point.y][point.x] && g_Map[point.y][point.x] < g_size) { if(time < g_time) { g_time = time; g_pish = POINT{point.x, point.y}; } else if (time == g_time) { if(point.y < g_pish.y) { g_pish = POINT{point.x, point.y}; } else if (point.y == g_pish.y) { if(point.x < g_pish.x) { g_pish = POINT{point.x, point.y}; } } } } g_queue_point.push(point); g_queue_level.push(time); }

제출 #86794

제출 정보

제출 결과

제출 코드

찾은 반례