BOJ. Baby Shark (16236)

Problem: BOJ 16236 — Baby Shark · 한국어 · 日本語

For each trip, run BFS from the shark’s current position. Cells containing fish larger than the shark are impassable; empty cells and cells with fish no larger than the shark can be entered. A fish is edible only when its size is strictly smaller than the shark’s. In particular, a fish of equal size can be crossed but cannot be eaten.

BFS visits cells in nondecreasing distance, so once an edible fish is found, only the rest of that distance layer can contain another equally near choice. Among those fish, choose the smallest row, then the smallest column. This directly implements the required ordering: shortest distance, then topmost, then leftmost. After reaching the selected fish, clear its cell, add the travel distance to elapsed time, and start a fresh BFS from there; the visited set is newly initialized for every trip.

The shark grows after eating a number of fish equal to its current size. Its size increases by one and the eaten-fish counter resets. If a BFS finds no edible fish, the simulation ends. Each trip takes O(N^2) time and O(N^2) space; with at most F fish eaten, the total is O(F N^2).

C++

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<vector<int>> grid(n, vector<int>(n));
  int sharkRow = 0;
  int sharkCol = 0;

  for (int r = 0; r < n; ++r) {
    for (int c = 0; c < n; ++c) {
      cin >> grid[r][c];
      if (grid[r][c] == 9) {
        sharkRow = r;
        sharkCol = c;
        grid[r][c] = 0;
      }
    }
  }

  const int dr[] = {-1, 0, 0, 1};
  const int dc[] = {0, -1, 1, 0};
  int sharkSize = 2;
  int eaten = 0;
  int elapsed = 0;

  while (true) {
    vector<vector<int>> distance(n, vector<int>(n, -1));
    queue<pair<int, int>> q;
    q.push({sharkRow, sharkCol});
    distance[sharkRow][sharkCol] = 0;

    int preyRow = -1;
    int preyCol = -1;
    int preyDistance = -1;

    while (!q.empty()) {
      const auto [r, c] = q.front();
      q.pop();
      const int d = distance[r][c];
      if (preyDistance != -1 && d > preyDistance) break;

      if (grid[r][c] > 0 && grid[r][c] < sharkSize) {
        if (preyRow == -1 || r < preyRow || (r == preyRow && c < preyCol)) {
          preyRow = r;
          preyCol = c;
          preyDistance = d;
        }
        continue;
      }

      for (int direction = 0; direction < 4; ++direction) {
        const int nr = r + dr[direction];
        const int nc = c + dc[direction];
        if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
        if (distance[nr][nc] != -1 || grid[nr][nc] > sharkSize) continue;
        distance[nr][nc] = d + 1;
        q.push({nr, nc});
      }
    }

    if (preyRow == -1) break;

    elapsed += preyDistance;
    sharkRow = preyRow;
    sharkCol = preyCol;
    grid[sharkRow][sharkCol] = 0;
    ++eaten;
    if (eaten == sharkSize) {
      ++sharkSize;
      eaten = 0;
    }
  }

  cout << elapsed;
}