글 읽기 - 예제 입력 5번 관련 질문

jamjari 1년 전 1

제가 이해한 바 대로 문제를 풀었더니 예제 입력 5번에 대한 답이 50으로 나와서 하나하나 어디 거쳐갔는지 보니 아래와 같이 나왔습니다.

found prey at 6, 6 (1) = 6 tick
found prey at 6, 1 (1) = 15 tick -> promote to size 3
found prey at 6, 2 (2) = 1 tick
found prey at 1, 3 (2) = 6 tick
found prey at 2, 5 (2) = 3 tick -> promote to size 4
found prey at 2, 3 (3) = 2 tick
found prey at 1, 6 (3) = 4 tick
found prey at 3, 6 (3) = 4 tick
found prey at 6, 4 (2) = 5 tick -> promote to size 5
found prey at 3, 3 (4) = 4 tick

손으로 풀어봐도 저 순서가 맞는 것 같은데 예시 출력은 48이네요,, 제가 문제를 잘못 이해한건가요?

#include <bits/stdc++.h>

using namespace std;

struct point {
  int y;
  int x;
  bool operator<(point& p) {
    if (y == p.y) return x < p.x;
    return y < p.y;
  }
};

const int BLOCKED = 999;
const array<point, 4> directions = {{ { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } }};

vector<point> bfs;
array<array<bool, 22>, 22> visited;
array<array<int, 22>, 22> sea;
int n, shark_size, ate_cnt, t;

bool can_eat(int y, int x) {
  return sea[y][x] < shark_size && sea[y][x] != 0;
}

bool prey_exists() {
  for (int i = 0; i < sea.size(); i++) {
    for (int j = 0; j < sea[i].size(); j++) {
      if (can_eat(i, j)) return true;
    }
  }
  return false;
}

bool can_move(int y, int x) {
  return sea[y][x] <= shark_size;
}

void eat(int y, int x) {
  sea[y][x] = 0;
  ate_cnt++;
  if (ate_cnt == shark_size) {
    shark_size++;
    ate_cnt = 0;
  }
}

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

  // initialize variables;
  for (int i = 0; i < 22; i++) {
    for (int j = 0; j < 22; j++) {
      sea[i][j] = BLOCKED;
    }
  }
  shark_size = 2;
  ate_cnt = 0;
  t = 0;

  // process inputs
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> sea[i][j];
      if (sea[i][j] == 9) bfs.push_back({ i, j });
    }
  }

  // solution
  bool found_prey;
  while (prey_exists()) {
    found_prey = false;
    for (int i = 0; i < visited.size(); i++) {
      for (int j = 0; j < visited[i].size(); j++) {
        visited[i][j] = false;
      }
    }
    while (!found_prey && !bfs.empty()) {
      t++;
      for (int i = bfs.size(); i > 0; i--) {
        point node = bfs.front();
        bfs.erase(bfs.begin());
        if (can_eat(node.y, node.x)) {
          eat(node.y, node.x);
          found_prey = true;
          bfs.erase(bfs.begin(), bfs.end());
          bfs.push_back({ node.y, node.x });
          t--;
          break;
        }
        for (point d : directions) {
          if (visited[node.y+d.y][node.x+d.x]) continue;
          if (can_move(node.y+d.y, node.x+d.x)) {
            bfs.push_back({ node.y+d.y, node.x+d.x });
            visited[node.y+d.y][node.x+d.x] = true;
          }
        }
      }
    }
  }
  cout << t << "\n";

	return 0;
}

yhj1937 1년 전 1

1, 6에서 3, 6으로 갈 때 2tick 입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예제 입력 5번 관련 질문

jamjari 1년 전 1

yhj1937 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말