#include #include using namespace std; int dr[4] = {-1, 1, 0, 0}; int dc[4] = {0, 0, -1, 1}; int cur_size = 2; int eated = 0; int sea[21][21]; int visited[21][21]; int n; pair shark; bool available() { // 작은 먹을 수 있는 애가 있나? for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (sea[i][j] != 0 && sea[i][j] < cur_size) { return true; } } } return false; } void init_visited() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { visited[i][j] = 0; } } } bool available_location(int r, int c) { if (r < 0 || r >= n || c < 0 || c >= n) return false; if (visited[r][c] != 0) return false; if (sea[r][c] > cur_size) return false; return true; } pair find_min() { int dist = 100000; pair rnt; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (visited[i][j] < dist && sea[i][j] != 0 && sea[i][j] < cur_size) { dist = visited[i][j]; rnt.first = i; rnt.second = j; } } } return rnt; } void bfs() { queue> q; init_visited(); q.push({shark.first, shark.second}); visited[shark.first][shark.second] = 1; while(!q.empty()) { int cur_r = q.front().first; int cur_c = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int next_r = cur_r + dr[i]; int next_c = cur_c + dc[i]; if (available_location(next_r, next_c)) { q.push({next_r, next_c}); visited[next_r][next_c] = visited[cur_r][cur_c] + 1; } } } } int sol() { int ans = 0; pair next_coor; while(available()) { bfs(); next_coor = find_min(); sea[next_coor.first][next_coor.second] = 0; // 먹음 eated++; if (eated == cur_size) { cur_size++; eated = 0; } shark.first = next_coor.first; // 상어 다음 위치 초기화 shark.second = next_coor.second; ans += visited[next_coor.first][next_coor.second] - 1; } return ans; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &sea[i][j]); if (sea[i][j] == 9) { shark.first = i; shark.second = j; sea[i][j] = 0; } } } printf("%d", sol()); return 0; }

제출 #116142

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: