Блог пользователя bradyawn

Автор bradyawn, история, 7 лет назад, По-английски

I'm writing code that takes in a "maze" and runs bfs. I have already solved it for small test cases, but the code for taking in input fails on large test cases.

Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2*H+1 lines with width 2*W+1 characters that represent the maze in a format like this:

Example of a 5X3 Maze
Example of a 25x25 Maze - Code Fails on This Input
Full Problem Statement

Issue: The loop that takes in the maze stops when i = 19 for the 25x25 maze.

EDIT: Clarification — "taken" will never be printed on the failing test case.

Any ideas what's causing this?

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please provide a Minimal, Complete, and Verifiable example. My assumption is that your program has undefined behavior somewhere later in the program and so it does not flush output buffer, therefore you do not see the taken line. Try removing everything except for the reading and see if the problem persists. If it does, remove more stuff.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, I commented out the bfs code/logic stuffs when I ran it. I will update it with a better example. EDIT: I updated it with a better example.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Your code works fine on Ideone. Do you have an environment where that exact code does not work?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        As for the problem, I am getting 'std::bad_alloc' which I thought was an input issue but it seems I am allocating too much memory. (Not sure how I am taking > 16MB though)

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          It may be the case that you try to pass something like -1 to an allocation function which converts that to an unsigned type which results in several billions. Try printing w and h in the very beginning to ensure that your reading is ok.