글 읽기 - C++ BFS 조언 부탁드립니다.

rkdbg11752 1년 전 0

1. 예외처리

2. dx, dy 값 오타

3. h, w 입력 순서와 사용 순서

세 가지를 중점적으로 체크해보았을 때 이상없다고 생각하는데 제가 보지 못한 오류가 있는 것 같습니다. 게시판의 테스트 케이스들도 체크해보았습니다.

제가 찾지 못한 오류에 대해 조언해주시면 감사드리겠습니다.

#define MAX 201

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

class Monkey
{
public:
  int x;
  int y;
  int horse;
  Monkey()
  {
    x = 0;
    y = 0;
    horse = 0;
  }
};

int k;
int w, h;
bool board[MAX][MAX];

int dx[4]{1, -1, 0, 0};
int dy[4]{0, 0, 1, -1};
int dxHorse[8]{1, -1, 1, -1, 2, -2, 2, -2};
int dyHorse[8]{2, 2, -2, -2, 1, 1, -1, -1};
int vis[MAX][MAX][31];
queue<Monkey> Q;

void showBoard(int k)
{
  for (int i{}; i < h; i++)
  {
    for (int j{}; j < w; j++)
    {
      cout << vis[i][j][k] << " ";
    }
    cout << "\n";
  }
}

void init()
{
  for (int i{}; i < MAX; i++)
  {
    for (int j{}; j < MAX; j++)
    {
      for (int k{}; k < 31; k++)
      {
        vis[i][j][k] = MAX;
      }
    }
  }
}

void bfs()
{
  while (!Q.empty())
  {
    Monkey cur{Q.front()};
    Q.pop();
    for (int i{}; i < 8; i++)
    {
      Monkey nxt{cur};
      nxt.x += dxHorse[i];
      nxt.y += dyHorse[i];
      nxt.horse++;
      if (nxt.x < 0 || nxt.x >= h)
        continue; // outOfMap
      if (nxt.y < 0 || nxt.y >= w)
        continue; // outOfMap
      if (board[nxt.x][nxt.y])
        continue; // obstacle
      if (vis[nxt.x][nxt.y][nxt.horse] != MAX)
        continue; // visited
      if (nxt.horse > k)
        continue; // overThanK
      Q.push(nxt);
      vis[nxt.x][nxt.y][nxt.horse] = vis[cur.x][cur.y][cur.horse] + 1;
    }
    for (int i{}; i < 4; i++)
    {
      Monkey nxt{cur};
      nxt.x += dx[i];
      nxt.y += dy[i];
      if (nxt.x < 0 || nxt.x >= h)
        continue; // outOfMap
      if (nxt.y < 0 || nxt.y >= w)
        continue; // outOfMap
      if (board[nxt.x][nxt.y])
        continue; // obstacle
      if (vis[nxt.x][nxt.y][nxt.horse] != MAX)
        continue; // visited
      Q.push(nxt);
      vis[nxt.x][nxt.y][nxt.horse] = vis[cur.x][cur.y][cur.horse] + 1;
    }
  }
}

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

  cin >> k;
  cin >> w >> h;
  for (int i{}; i < h; i++)
  {
    for (int j{}; j < w; j++)
    {
      cin >> board[i][j];
    }
  }

  init();
  Monkey st = Monkey();
  Q.push(st);
  vis[st.x][st.y][st.horse] = 0;
  bfs();

  // cout<<"\n";
  // for(int i{}; i<=k; i++) {
  //   showBoard(i);
  //   cout<<"\n";
  // }

  int ans{*min_element(vis[h - 1][w - 1], vis[h - 1][w - 1] + k + 1)};
  if (ans == MAX)
    ans = -1;
  cout << ans;

  return 0;
}

siyamaki 1년 전 1

맵의 초기화를201로 하시면 201번째 이동에 맵 끝에 도착을 하거나 H W가 200이고 K가 30이면 전부 빈 공간일 때 338번만에 도착점으로 이동할 수 있습니다.

rkdbg11752 1년 전 0

아.. 안일한 초기화가 잘못이었네요. 오류를 찾아주셔서 감사드립니다.

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

문제

문제

출처

ICPC

C++ BFS 조언 부탁드립니다.

rkdbg11752 1년 전 0

siyamaki 1년 전 1

rkdbg11752 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말